Meghatározása a grafikon, H4S

Irányítatlan gráfot hat csúcsok és hét élek

A matematikai gráfelmélet és a számítógép grafikon - egy sor nem üres csúcsok halmaza, és egy sor pár csúcsot.

Az objektumok képviseletében a csúcsot. vagy grafikon csomópontok és kapcsolatok - mint ív. vagy a bordák. A különböző alkalmazások, különböző típusú grafikonokat orientált, korlátozások a kapcsolatok száma, és további adatokat a csúcsok és élek.

Sok struktúrák gyakorlati érdeklődés a matematika és számítástechnika, leírható grafikonok. Például, Wikipedia szerkezete lehet modellezni egy irányított gráf (digráf), amelyben a felső - ezt a cikket, és a ívek (orientált szélek) - hiperhivatkozásokat (lásd tematikus térkép.).

meghatározzák

• V egy nem üres csúcsok halmaza vagy csomópontok,
• E a párok halmaza (abban az esetben, egy irányítatlan gráf - rendezetlen) csúcsok, úgynevezett élek.

V (és így E. különben nem lenne multihalmazt) általában úgy tekintik, hogy véges halmazok. Sok jó eredményeket véges gráf, helytelen (vagy bármilyen módon eltérő) a végtelen gráfok. Ez azért van, mert számos olyan szempontot, hogy hamis az esetben végtelen halmazok.

Csúcsok és az élek a grafikon is nevezik elemei a gráf csúcsainak számát egy grafikonon | V | - sorrendben. élek száma | E | - a méret a grafikonon.

Csúcsok u és v nevezzük végpontok (vagy vége) élek e = u, v>. Edge, viszont összeköti a tetején. Két végén csúcsai azonos borda nevezzük szomszédok.

Két élek úgynevezett szomszédos. ha van egy közös vége csúcs.

Két élek nevezzük többszörösei. amennyiben több végén csúcsok egybeesnek.

Egy él az úgynevezett hurok. Ha a végén ugyanaz, azaz, e = v, v>.

Degree ° V V csúcsok említett élek számát, amelyre ez egy vége (a hurok tekintjük kétszer).

Vertex nevezzük izolált. ha ez nem a végén semmilyen fin; lógó (vagy lemez), ha az a vége pontosan egy szélét.

irányított gráf

Arc - rendezett pontpár (v, w). ahol a v csúcs hívják az elején, és w - arc végén. Elmondhatjuk, hogy az ív vezet egy v csúcs Vertex w.

vegyes Count

Vegyes grafG - egy grafikon, amelyben néhány éleket lehet orientált, és néhány - irányítatlan. Felvett megrendelt hármas G. = (V, E, A), ahol a V. E és A jelentése ugyanaz, mint fent.

Orientált és nem orientált grafikonok speciális esetei összekeverjük.

izomorf gráfok

Gráf úgynevezett izomorf gráf H. Ha van bijekciót f a több csúcs G gráf H. több csúcsot, amely a következő tulajdonság: ha a G gráf egy él a csúcspont a vertex A grafikonon B. H kell lennie egy él a csúcspont F ( a) a felső f (B), és fordítva -, ha a tér H egy éle a vertex csúcsából B. grafeG amely szegélynek a vertex f - 1 (a) a vertex f - 1 (B). Ebben az esetben, az irányított gráf kell fenntartani bijekciót orientáció borda. Abban az esetben, súlyozott gráf bijekciót is meg kell őriznie bordák tömeg.

Egyéb kapcsolódó definíció

Path (vagy lánc) a gráf egy véges sorozat csúcsok, ahol mindegyik csúcs (kivéve az utolsó) össze van kötve a következő a szekvenciája csúcsai a szélét.

Orientált által digráf véges sorozata csúcsok vi, amely minden pár (vi, vi + 1) vannak (orientált) szélei.

A ciklus egy könyvtárat, ahol az első és az utolsó csúcsai azonos. Amikor etomdlinoy path (vagy a ciklus) az a szám, amely az azt alkotó élek. Megjegyezzük, hogy ha a csúcsok u és v értéke a végei egy él, akkor szerint a definíció szerint, olyan szekvenciát (u, v, u) egy ciklust. Annak elkerülése érdekében, az ilyen „degenerált” esetben be az alábbi fogalmakat.

Az ösvény (vagy ciklus) nevezzük egyszerű. ha az élek ott nem ismétlődnek; elemi. ha ez egy egyszerű és csúcsok azt nem ismételjük. Könnyen belátható, hogy:

• Minden módon köti össze a két csúcsot tartalmaz elemi út, amely összeköti az azonos két csúcs.
• Minden egyszerű útvonal tartalmaz, nem elemi elemi ciklus.
• Minden egyszerű ciklus, áthalad egy csúcs (vagy borda) soderzhitelementarny (al) hurok, amely áthalad az ugyanazon vertex (vagy él).
• Loop - elemi ciklus.

A bináris reláció a csúcsok halmaza megadott „van egy út a u v», egy ekvivalencia reláció. és ezért megtöri a sor ekvivalencia osztályok, az úgynevezett összetevői a grafikonon. Ha a szám pontosan egy csatlakoztatott készülék a gráf összefüggő. A csatlakoztatott készülék is be ponyatierasstoyaniya közötti csúcsok, mint a minimális hosszúságú út, amely összeköti ezeket a csúcsokat.

Minden maximális csatlakoztatva részgráfja G gráf egy csatlakoztatott komponens (vagy komponens) a gráf A „maximális” jelenti a felvétel egy maximális, amely nem tartalmaz egy csatlakoztatott részgráfot nagy számú elemet

Edge of a gráf úgynevezett hídon. ha törlés növeli a komponensek száma.

További jellemzői grafikon

• csatlakoztatva. ha bármely két u, v csúcsokhoz egy út u-ból v.
• orientált erősen összefüggő vagy csatlakoztatva. ha orientált, és minden csomópont bármely más van egy irányított út.
• fa. Ha csatlakoztatva van, és nem tartalmaz egyszerű ciklusokat.
• teljes. ha bármely két (magas, ha a hurok nem megengedett), a csúcsokat összekötve a szélén.
• páros. ha a csúcsait feloszthatjuk két diszjunkt részhalmaza V1 és V2, hogy minden él köti csúcsa egy vertex V1 V2.
• k-Dolny. ha a csúcsait feloszthatjuk k diszjunkt részhalmazai V1, V2. ..., Vk, hogy nem lesz összekötő élek csúcsai azonos részhalmaza.
• teljes páros. ha minden csúcsa egy részhalmaza van csatlakoztatva, hogy él egymással vertex részhalmaza.
• sík. ha a gráf által képviselt diagram a gépen keresztezése nélkül élek.
• súlyozott. Ha minden él van rendelve egy bizonyos számú úgynevezett tömeg szélén.

Ways, hogy képviselje a grafikon a számítástechnikában

A szomszédsági mátrix

Táblázat ahol az oszlopok és a sorok felelnek meg a csúcsai a grafikon. Az egyes cellákban a mátrix számát feljegyezzük, jelzi, hogy a kommunikáció a felső sorban a tetején az oszlop (vagy fordítva).

Hátránya a memóriaigény egyenesen arányos a tér a csúcsok száma.

• A két-dimenziós tömb;
• Matrix hiányosságokat;
• Az implicit referencia (az eszköz használatával).

előfordulási mátrix

Mindegyik vonal megfelel egy adott csúcsa a grafikon, és az oszlopok a kapcsolatok grafikon. A cella i-edik összhangban a j-edik oszlopa a mátrix van írva:

1, ha a kapcsolat j «ki» a vertex i. -1, ha a kapcsolat a „rész” a felső, 0 minden más esetben (azaz, ha a kapcsolat egy hurok, vagy a kommunikáció nem beeső tetejére)

Ez a módszer a legtöbb tágas (méret arányos | E | | V |), a tárolás, de megkönnyíti, hogy megtalálja ciklusban a grafikonon.

listája bordák

Listája élek - egy olyan típusú gráf a memóriában egy számítógépes program, azt értjük, hogy minden élét, amit két szám - a számok a borda tetejét. Listája bordák sokkal kényelmesebb, hogy végre különböző algoritmusok grafikonok, míg a szomszédsági mátrix.

Az általánosítás fogalmának grafikon

Több elvont a grafikon lehet meghatározni, mint három (V, E, φ), ahol V és E - Néhány készletek (csúcsok és az élek ill ..), és - a függvénye előfordulása (vagy incidentor), amely kijelöli az egyes él (rendezett vagy rendezetlen) pár vershinu és v v (az egészet). Különös esetekben ez a fogalom a következők:

• irányított gráf (digraphs) -, ha φ (e) mindig egy rendezett pár csúcsok;
• irányítatlan gráfok - ahol φ (e) mindig rendezetlen pontpár;
• vegyes grafikonok - ahol egyaránt vannak irányítva, és irányítatlan élek és hurkok;
• Euler grafikonok - grafikont, amelyben van egy kör alakú pálya Euler (Euler ciklus).
• multigráfokra - grafikonok többszörös élek, amelyek a végeik azonos pontpár;
• pseudographs - ez multigráfokra bevallja létezését hurkokat
• egyszerű gráfok - anélkül, hurkok és többszörös élek.

A meghatározás nem illik néhány más általánosítások megadott:

irodalom