ALKALMAZOTT MATEMATIKAI LAPOK 2. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1976)

1976 / 3-4. sz. - Kovács László Béla és Dienes István: Maximum tranzitív utak és alkalmazásuk egy geológiai problémára: rétegtani egységek létrehozása

Alkalmazott Matematikai Lapok 2 (1976) 157—114 MAXIMUM TRANZITÍV UTAK ÉS ALKALMAZÁSUK EGY GEOLÓGIAI PROBLÉMÁRA: RÉTEGTANI EGYSÉGEK LÉTREHOZÁSAI KOVÁCS LÁSZLÓ BÉLA és DIENES ISTVÁN Budapest Egy geológiai probléma tanulmányozása új gráfelméleti problémához, egy irányított gráf ún. maximum tranzitív útjainak meghatározásához vezetett. Először a tranzitív utak néhány alap­vető tulajdonságát mutatjuk be. Ezután részfeladatokat jelölünk ki és ezekre megoldó eljárásokat írunk le. Bizonyos, csúcspárokra vonatkozó mérőszámok bevezetése és vizsgálata is az alapprobléma megoldását segíti elő. A kiindulásul szolgáló geológiai problémát röviden vázoljuk és kitérünk a Dorogi medence adataival végzett kísérleti eredményekre is. 1. Bevezetés A jelen dolgozat elsősorban egy adott irányított gráf maximum tranzitív út­jainak meghatározásával foglalkozik. A tranzitív út az irányítatlan gráfokra defini­ált teljes algráf fogalmának egy lehetséges kiterjesztése irányított gráfokra. Ennek az új fogalomnak a bevezetésére geológiai kutatásainkkal kapcsolatban volt szükség, amelyet röviden a 2. szakaszban vázolunk. Ezután következik az alapprobléma felvetése, majd a tranzitív utak néhány fontos tulajdonsága. Az 5.—7. szakaszok az alapfeladat megoldását elősegítő néhány részfeladatot írnak le és megoldásukra szolgáló eljárásokat vázolnak. Itt szerepel a maximum teljes részgráf keresés mint relaxáció, a csúcspárok kapcsolati száma és egy dekompo­zíciós eljárás. A 8. szakasz bemutat egy egzakt illetve egy heurisztikus eljárást, melynek segítségével elhagyhatók azok a csúcsok, amelyek nincsenek egyetlen optimális megoldásban sem, illetve a heurisztikus eljárás esetében nem valószínű, hogy benne vannak. A 9. szakasz az alapfeladat megoldására szolgáló, korlátozás és szétválasztás elvén működő, eljárás főbb tulajdonságait ismerteti. Végül a 10. szakasz a Dorogi medencével kapcsolatos jelenlegi vizsgálataink fő célkitűzéseit és eddigi kísérleti eredményeit vázolja. Alapfeladatunk relaxációja, egy irányítatlan gráf maximum teljes részgráfjainak meghatározása, közvetlenül is megoldható [3, 4] valamint halmazlefedési feladat­ként is [2, 10, 12—16]. Megjegyzendő azonban, hogy a jelen dolgozatban vázolt sok gondolat, illetve eljárás jól felhasználható mind erre, mind más erősen struk­túrált diszkrét feladat megoldására — így a teljes algráf problémára is, különösen, ha csak a legnagyobb elemszámú azaz maximum teljes részgráfokat keressük. 1) Ez a dolgozat a IX. Nemzetközi­­Matematikai Programozási Szimpóziumon (Budapest, 1976) elhangzott előadás Írásbeli változata. 5* Alkalmazott Matematikai Lapok 2 (1976)

Next