Alapfogalmak és meghatározások gráfelmélet - studopediya
Grafikonok és képviseletüket a számítógép memóriájában.
Alapfogalmak és meghatározások gráfelmélet
Gráfelmélet egyik ága a matematika, amely nagy gyakorlati alkalmazása. Ami a kialakított számos kapcsolatos problémák különálló objektumok. Az ilyen problémák merülnek fel a tervezés az integrált áramkörök és vezérlő áramkörök, elektromos áramkörök, folyamatábrák, a gazdaság, a statisztika, a kémia, a biológia és más területeken. Gráfelmélet vált az egyik alapvető része a matematikai apparátus kibernetika, a nyelv a diszkrét matematika.
Probléma 1. Város Kenigsberg, keleti részében helyezkedik el Poroszország épült torkolatánál a két folyó partján a saját, és a két sziget. A város volt hét hidak, amelyek összekötik a szigeteket, hogy egymással és a part menti része a város (3.1 ábra). Meg kell válaszolni a kérdésre: hogyan lehetne bármely polgárának Königsberg, kijött a házból, menjen végig a hét hidat a város pontosan egyszer haza?
A válasz a feltett kérdésre ezt a problémát kell lennie a negatív. Euler adta ezt a választ, és megállapította, hogy létezik a útvonal kritérium követelményeinek megfelelő a feladat.
Azonban a kapott eredményt Euler, több mint száz éve volt az egyetlen eredmény gráfelmélet.
Fejlesztési gráfelmélet a késő XIX és XX század elején. Ez járt a terjedését ötletek a molekuláris anyag szerkezetének kialakulásához és az az elmélet az elektromos áramköröket. Ezzel az évben a 50. századunk gráfelmélet dolgoztunk két különböző területen: algebrai és optimalizálása.
Például, a keresés a választ, hogy az adott probléma 1 utal az irányt a algebrai gráfelmélet. Szerkesztése 1. feladat.
Probléma 2 A különbség a probléma 2 A feladat 1 mi azt, hogy talál egy útvonalat, hogy a belföldi, kijött a házból, kerül sor minden hidat legalább egyszer, és vissza fog térni haza a az útvonal hossza minimálisra kell csökkenteni.
A feladat megtalálni egy ilyen útvonal utal optimalizálása irányába gráfelmélet.
Adunk a meghatározása a grafikonon. Legyen V - nem üres halmaza, V - a készlet minden kételemű részhalmaza. A páros (V, E), ahol E ÍV nevezzük egy grafikon (irányítatlan gráf).
Egy gráf véges. Ha a beállított V véges. A jövőben a „grafikon” értünk egy véges gráf.
több V elemek nevezzük a gráf, és E elemeit nevezzük élei a grafikon.
A csúcsok száma egy gráf G = (V, E) nevezzük annak érdekében.
Kezdve a meghatározása a grafikon, mindegyik él megfelel a két-elemű részhalmaza csúcsok. Ha egy részhalmaza v1, v2> felel meg e él. Azt mondjuk, hogy egy él e az eset, hogy a vertex V1 és V2. és a csúcsokat v1 és v2smezhny. Azt is mondják, hogy egy él e összeköti a csúcsokat a V1 és V2. A csúcsok a v1 és v2 nevezzük végpontjai e él.
Egy gráf ábrázolható grafikusan ábrázoltuk minden egyes vertex pont vagy egy kört, és az egyes lábak tűnik összekötő szakasz terminális csúcs.
Bármilyen gráf lehet tekinteni, mint egy sor összekapcsolt grafikonok. Mindegyik grafikonok hívott komponens az eredeti gráf.
Disconnected grafikon ábrán látható. 3.9 két összetevője van.
Állítsa be a ívű, a kizárásra a grafikon számát növeli annak összetevői, az úgynevezett vágott.
Egy gráf ábrán látható. 3.9, a vágás van allokálva ív e. mivel a törlés növeli a komponensek száma a két.
Legyen G = (V, E), V ¢ÍV, akkor a grafikon, a csúcsok halmaza egybeesik V ¢, és magában foglalja a több ívek összes több ív E-terminált csúcsok v ¢, úgynevezett részgráfot G. nemző V ¢.
Legyen E ¢ÍE. akkor a száma, amelyek egy sor ívek egybeesik E ¢, és a csúcsok halmaza tartalmaz csúcsok beeső ívei E ¢, úgynevezett részgráfja G, nemzett E ¢.
Egy gráf teljes, ha bármely két csúcsa szomszédos.
Egy gráf azt mondják, hogy üres. ha nincsenek élek.
Grafikon, amely nem tartalmaz ciklust nevezzük gyűrűs.
Connected irányítatlan gráf aciklikus nevezzük fa. set fák nevezzük erdőben.
Ha az élek teszik ki a fát, és helyére irányított ív, megkapjuk irányított fa. Hacsak összefüggésben világos, hogy mi a fa kérdéses, hogy a jövőben a „koncentrált” elhagyjuk.
Egy irányított fa van értelme, hogy a koncepció a gyökér. Minimális teljesítmény-orientált csúcsok halmaza a fa, amelyből van mód az összes többi csúcs, az úgynevezett set gyökereit.
Bevonat (spanning) G fagráf egy fa, amely egy részgráfját G, és tartalmaz minden csúcsához.
Ha G nincs csatlakoztatva, a beállított álló fő fák egyes komponensek, úgynevezett kiterjedő (spanning) erdő.
Általánosítása a gráf hipergráf.
A hipergráf. Ellentétben a gráf élei lehet nem csak egy-két darabot, de olyan részhalmaza csúcsot.
Ezek a tárgyak a matematika ismert hosszú ideig, de a bevezetése a „hipergráfban” társított sikeres rájuk számos fontos fogalmak és módszerek gráfelmélet.
3.1.2. P redstavlenie grafikonok a számítógép memóriájában
Bármilyen gráf lehet képviselve mátrix formában.
Az ábrán látható grafikonon adjuk. 3.5, a szomszédsági mátrix képviseli a 3.1 táblázatban.
Megjegyezzük, hogy irányítatlan gráf szomszédsági mátrix szimmetrikus az főátlójában azaz a számítógép memóriájában tárolja elegendő csak a fele a mátrixban.
a grafikon szomszédsági mátrix, látható Fig.3.5
A gyakorlatban igen gyakran használt mátrixokat képviselő grafikonok teljesen lemerült, vagyis amelyek sok karakter „0” vagy „¥”. Ez szükségtelen költségeket memóriában tárolja ezeket a mátrixokat a számítógépbe.
Memória kapacitása jelentősen csökkenthető, ha a csomagolás mátrix listákat egymásba típusát.
Példa csomagolás tekinthető súlyok mátrixa (lásd 3.3.) Az egymásba ágyazott egy listában típusú, végrehajtott három vektorok (tömbök) látható ris.3.10.
Ahhoz, hogy megtalálja a csúcsokat szomszédos vertex i -edik és súlyok megfelelő ívek egy ilyen szerkezet kiszámításához szükséges a kezdeti és a végső In Ik kódok a vektorokban V. és S képletekkel összhangban
Csomagolják tárolás és ezáltal súlyozó mátrix szüksége lesz egy 42 memória cella tömbök által elfoglalt V, S, és U. csomagolatlan mátrix elfoglalt 10'10 = 100 memóriahely.
Ris.3.10. Csomagolás weight mátrix (táblázat. 4.3) a foglalat típusa lista
Végrehajtásakor algoritmusok, amelyben az eredeti gráf változások (hozzáadni vagy eltávolítani csúcsokat, és így tovább) tárolására grafikonok néha kényelmesebb használni a szomszédsági listák. Szomszédossági lista valósítható létrehozása révén lineáris lista n lineáris listák, ahol n - a csúcsok számát.
Az ábrán látható grafikonon adjuk. 3.7, a szomszédsági lista ábrán bemutatott. 3.11.
Egy másik módja, hogy tárolja grafikonok - a lista élek, vagyis a lista, amely felsorolja azokat a széleit a grafikonon.
Listája gráf élek, ábrán látható. 3.7 ábrán látható. 3.12.
List bordák végrehajtott három tömböt, és elfoglalja 48 sejtekben. Az is lehetséges, hogy használja ahelyett, hogy a tömbök lista szerkezetét.
A választás a kódolási módszer a grafikon és adatszerkezetek annak végrehajtására függ az adott feladat algoritmusa a megoldások lehetséges bemeneti adatok, valamint az egyes programozó hajlamait.