A gráfelmélet a tudományág matematikája és számítógépe , amely a grafikonokat tanulmányozza , amelyek az objektumokat összekötő hálózatok rajzainak absztrakt modelljei. Ezek a modellek a csúcsok (más néven csomópontok vagy pontok , a polihedrákra hivatkozva ) és az élek (más néven linkeknek vagy egyeneseknek ) adatait alkotják e csúcsok között; ezek az élek néha nem szimmetrikusak (a gráfokat akkor mondják orientáltnak ), és nyilaknak vagy íveknek nevezzük őket .
Az ezen elmélet tárgyait érintő problémák megoldására kifejlesztett algoritmusoknak számos alkalmazásuk van a hálózat ( szociális hálózat , számítógépes hálózat , telekommunikáció stb.) Fogalmához kapcsolódó területeken és számos más területen (pl. Genetikai ), mint a grafikon fogalma. , nagyjából egyenértékű a bináris relációval (nem tévesztendő össze egy függvény grafikonjával ), általános. Nagy és nehéz tételek, mint például a négy szín tétel , a perfekt gráf tétel , vagy akár a Robertson-Seymour tétel , segített létrehozni ezt a témát matematikusok és a kérdéseket hagy nyitva, mint például a sejtés Hadwiger , make a diszkrét matematika élő ága .
A gráfelméletben a gráfok meghatározásában számos variáció létezik. A leggyakoribb meghatározások a következők.
A kifejezés korlátozott, de nagyon elterjedt értelmében a gráf egy G = ( V , E ) pár , amely a következőket tartalmazza:
A kétségek elkerülése érdekében az ilyen típusú objektumokat pontosan egyszerű, irányítatlan gráfnak nevezhetjük .
Az { x , y } élben az x és y csúcsokat az él végének vagy szélső csúcsának nevezzük . Azt mondjuk, hogy a szélén csatlakozik x és y , és az eset a x és y . Egy csúcs létezhet egy gráfban beeső él nélkül. A több él két vagy több él, amelyek ugyanazt a két csúcsot egyesítik; nem létezhetnek egyszerű irányítatlan gráfban.
A több élt lehetővé tevő kifejezés általánosabb értelmében a gráf egy G = ( V , E , ϕ ) triplett , amely
A kétségek elkerülése érdekében az ilyen típusú objektumot pontosan irányíthatatlan multigráfnak nevezhetjük .
A hurok olyan él, amely egy csúcsot egyesít önmagával. A két előző definíció szerint definiált grafikonoknak nem lehetnek hurkok, mert az x csúcsot összekötő hurok él (egyszerű irányítatlan gráf esetén) vagy beesik (irányítatlan többgráf esetén) { x , x } = { x }, amely nem {{ x , y } | -ban ( x , y ) ∈ V 2 ∧ x ≠ y} . Tehát a ciklusok engedélyezéséhez ki kell terjeszteni a definíciókat. Egyszerű irányítatlan grafikonok esetén E ⊆ {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} -nak E become {{ x , y } | ( x , y ) ∈ V 2 } . Irányítatlan multigráfok esetén ϕ : E → {{ x , y } | ( X , y ) ∈ V 2 ∧ x ≠ y} kell válnia φ : E → {{ x , y } | ( x , y ) ∈ V 2 } . A kétség elkerülése érdekében az ilyen típusú objektumokat pontosan irányíthatatlan, egyszerű hurkokkal rendelkező gráfoknak, illetve hurkokkal rendelkező irányítatlan többgráfoknak nevezhetjük .
V-t és E- t általában feltételezzük végesnek, és sok eredmény megszűnik igaznak lenni (vagy különböző állításokkal rendelkezik) a végtelen gráfokra, mert egyes bizonyító érvek nem fordítanak végtelen esetre. Sőt, V- t gyakran feltételezzük, hogy nem üres, de E lehet az üres halmaz. A grafikon sorrendje | V | a csúcsainak száma. A grafikon mérete | E |, éleinek száma. A csúcs mértéke vagy vegyértéke az adott csúcsra eső élek száma, ahol a hurok duplája számít.
Egy egyszerű, irányítatlan n sorrendű gráfban a csúcs maximális mértéke n - 1 , a gráf maximális mérete pedig n ( n - 1) / 2 .
Az élek E egy irányítatlan gráf G indukálnak szimmetrikus bináris reláció ~ V úgynevezett adjacencia kapcsolatban a G . Pontosabban, mindegyik { x , y } élnél azt mondják, hogy az x és y szélső csúcsai szomszédosak egymással, amelyet x ~ y- vel jelölünk .
Az irányított gráf az a gráf, amelyben az élek tájolása van.
A kifejezés korlátozott, de nagyon elterjedt értelmében az irányított gráf egy G = ( V , A ) (néha G = ( V , E ) ) pár, amely
A kétségek elkerülése érdekében az ilyen típusú objektumokat pontosan irányított egyszerű gráfnak nevezhetjük .
A nyíl ( x , y ) orientált a x a y , x az úgynevezett farok a nyíl és y a fejét a nyíl. A nyíl ( y , x ) az úgynevezett inverz nyíl a ( x , y ) .
A több nyilat lehetővé tevő kifejezés általánosabb értelmében az irányított gráf egy G = ( V , A , ϕ ) (néha G = ( V , E , ϕ ) ) triplett , beleértve
A kétségek elkerülése érdekében az ilyen típusú objektumokat pontosan orientált multigráfnak nevezhetjük .
Az előző két definícióban definiált irányított gráfoknak nem lehetnek hurkok, mert az x csúcsot összekötő hurok a nyíl (egyszerű irányított gráf esetén) vagy egy (irányított multigráf esetén) ( x , x ) felé esik, amely nincs a { ( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} . Tehát a ciklusok engedélyezéséhez ki kell terjeszteni a definíciókat. Egyszerű orientált grafikonok esetén A ⊆ {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} -nak A ⊆ V 2- vé kell válnia . Orientált multigráfok esetén ϕ : A → {( x , y ) | ( X , y ) ∈ V 2 ∧ x ≠ y} kell válnia φ : A → V 2 . A kétség elkerülése érdekében az ilyen típusú objektumokat pontosan egyszerű, hurkokkal ellátott, irányított gráfoknak, illetve hurkokkal (vagy tegezekkel ) ellátott, irányított multigráfoknak nevezhetjük .
A hurkokkal ellátott egyszerű irányított gráf homogén összefüggés ( bináris viszony halmaz és saját maga között). Egy egyszerű irányított gráf, hurkok a G = ( V , A ) nevezzük szimmetrikus , ha minden egyes nyíl Egy , a megfelelő inverz nyíl is A .
Három fő grafikoncsalád és öt kategória van:
Leonhard Euler svájci matematikus 1735-ben a szentpétervári akadémiának bemutatott, majd 1741-ben megjelent cikke a hét königsbergi híd problémájával foglalkozott , az alábbiakban sematikusan. A probléma az volt, hogy megtaláltunk egy sétányt egy adott pontról, amely visszatér arra a pontra, amely egyszer és csak egyszer halad át Königsberg város hét hídján. Bármely hegygerincen pontosan egyszer áthaladó utat euleri útnak , vagy euleri körnek neveztek , ha az ott kezdődik, ahol elkezdődött. Tágabb értelemben egy Euler-kört befogadó gráfot Eulerian-gráfnak nevezünk , amely tehát a gráf első tulajdonságesete. Euler úgy fogalmazott, hogy a gráf csak akkor Eulerianus, ha minden csúcsnak páros élei vannak. A szokás az, hogy Euler-tételként emlegetik , bár a bizonyítást csak 130 évvel később, a német matematikus, Carl Hierholzer nyújtotta be . Hasonló probléma az, hogy az egyes csúcsokat pontosan egyszer kell átmenni, és először azzal a különleges esettel oldották meg, hogy egy lovagnak egy sakktábla minden négyzetét meg kell látogatnia Al-Adli arab sakktéma -elméletírójának, a Kitab ash -shatranj 840 körül megjelent munkájában és elveszett azóta. A lovag körútját a XVIII . Században részletesebben tanulmányozta Alexandre-Théophile Vandermonde francia matematikus , Pierre Remond de Montmort és Abraham de Moivre ; Thomas Kirkman brit matematikus tanulmányozta az útvonal általánosabb problémáját, ahol egy csúcson csak egyszer lehet áthaladni, de egy ilyen út végül William Rowan Hamilton ír matematikus után vette el a Hamilton-út nevet , és bár ez utóbbi csak egyetlen konkrét esetet tanulmányozott. Ezért megadjuk Eulernek a gráfelmélet eredetét, mert ő javasolta elsőként a kérdés matematikai kezelését, majd Vandermonde következett.
A XIX . Század közepén Arthur Cayley brit matematikus érdeklődött a fák iránt , amelyek egy olyan különféle grafikonok, amelyekben nincs ciklus, vagyis lehetetlen visszatérni a kiindulási ponthoz anélkül, hogy megtennék a fordított utat. Különösen az n csúcsú fák számát tanulmányozta, és megmutatta, hogy vannak ilyenek . Ez a " felsoroló kombinatorika egyik legszebb képlete " volt, ez a mező egy véges halmaz elemeinek számlálásából állt, és utat nyitott bizonyos tulajdonságokkal rendelkező grafikonok felsorolásához is. Ezt a kutatási területet valóban George Pólya magyar matematikus kezdeményezte , aki 1937-ben publikálta a nevét viselő számlálási tételt , és Nicolaas Govert de Bruijn holland matematikus . Cayley munkájához, akárcsak Polyához, alkalmazhatók voltak a kémia területén, és James Joseph Sylvester angol matematikus , a Cayley társszerzője 1878-ban bevezette a kémián alapuló "grafikon" kifejezést:
„Lehet, hogy a Természet olvasói számára nem teljesen érdekes, ha tisztában vannak egy hasonlósággal, amely nemrégiben nagy benyomást tett rám az emberi tudás olyan ágai között, amelyek láthatóan ugyanolyan különböznek, mint a kémia és a modern algebra. […] Minden invariáns és kovariáns tehát egy Kékuléan-diagrammal vagy kemikográffal pontosan megegyező gráffal válik kifejezhetővé. "
A gráfelmélet egyik legismertebb problémája a gráf színezése , ahol a cél az, hogy meghatározzuk, hány különböző szín elegendő egy gráf teljes színezéséhez, hogy egyetlen csúcs sem egyezzen meg a szomszédaival. 1852-ben Francis Guthrie dél-afrikai matematikus testvérével folytatott megbeszélés során meghatározta a négy szín problémáját , aki Auguste De Morgan tanárától azt kérdezte, hogy egy térképet négy színnel lehet-e színezni úgy, hogy a szomszédos országoknak más legyen a színe. De Morgan először levelet írt William Rowan Hamilton ír matematikusnak , akit nem érdekelt, majd Alfred Kempe angol matematikus téves bizonyítékokat tett közzé az American Journal of Mathematics-ban , amelyet Sylvester épp most alapított. Ennek a problémának a vizsgálata számos fejleményhez vezetett a gráfelméletben Peter Guthrie Tait , Percy John Heawood , Frank Ramsey és Hugo Hadwiger részéről .
A problémák a faktorizációja grafikonok így alakult végén a XIX E században is érdekel a átívelő részgráfok, vagyis a grafikonok, amely az összes csúcsot azonban csak egy részét az élek. A terjedő részgráfot akkor nevezzük k- faktornak, ha minden csúcsának van k éle, és az első tételeket Julius Petersen adta meg ; például megmutatta, hogy egy gráf akkor és csak akkor bontható 2 tényezőre, ha az összes csúcs páros számú éllel rendelkezik (de 50 évbe telt, amíg Bäbler foglalkozott a páratlan esettel). Ramsey színezéssel kapcsolatos munkája, különös tekintettel Pal Turan magyar matematikus eredményeire , lehetővé tette a szélsőséges grafikonok elméletének kidolgozását, amelyek olyan grafikonokra összpontosítottak, amelyek elérték az adott mennyiség maximumát (például az élek számát) adott korlátozásokkal, mint pl. bizonyos részgráfok hiánya.
A XX . Század második felében Claude Berge francia matematikus hozzájárul a gráfelmélet fejlődéséhez azáltal, hogy tökéletes gráfokkal járul hozzá és bevezeti a hipergráf kifejezést (Jean-Marie Pla megjegyzéseit követve, amikor egy szeminárium) a témával foglalkozó monográfiával. A gráfelméletről szóló bevezető könyve szintén eredeti alternatívát kínált, amely inkább személyes sétát, mint teljes leírást tartalmaz. Jelölni fogja ezen a területen a francia kutatást is: Marcel-Paul Schützenbergerrel közösen létrehoznak egy heti szemináriumot a Henri Poincaré Intézetben, hétfőnként találkoznak a Maison des Sciences de l'Homme-ban, és a kombinatorikus csapat vezetése Párizs.
A németek, Franz Ernst Neumann és Jacobi fizikus, illetve matematikus szemináriumok sorozatát alapították 1834-ben. Gustav Kirchhoff német fizikus volt az egyik diák, aki 1843 és 1846 között részt vett a szemináriumon, és kiterjesztette Georg Ohm munkáját 1845-ben Kirchhoff törvényeinek megalkotására, amelyek kifejezik az energia és töltés megőrzését egy elektromos áramkörben . A csomópontok törvénye kimondja, hogy a csomópontba belépő áramok intenzitásának összege megegyezik azzal, amely elhagyja azt. Az elektromos áramkör grafikonnak tekinthető, amelyben a csúcsok az áramkör csomópontjai, és az élek megfelelnek az e csomópontok közötti fizikai kapcsolatoknak. Az áramkörön átáramló áramok modellezéséhez úgy gondoljuk, hogy minden élt át tud keresztezni egy áramlás . Ez számos analógiát kínál, például a folyadék, például a víz csatornahálózaton keresztül történő áramlásával vagy az úthálózatban történő keringéssel. A csomópontok törvénye előírja, hogy a csúcson az áramlás megmarad, vagy azonos a bejáratnál, mint a kijáratnál; például a csatornába belépő víz nem tűnik el, és a csatorna nem termel ilyet, ezért annyi víz távozik, mint ahány belép. Ezenkívül egy élnek van kapacitáskorlátja, ahogyan egy csatorna bizonyos maximális vízmennyiséget is képes szállítani. Ha hozzátesszük, hogy az áramlás egy bizonyos csúcsnál (a forrásnál ) kezdődik, és hogy egy másiknál (a süllyedőn ) ér véget , akkor az áramlások vizsgálatának alapelveit grafikonon kapjuk meg.
Ha figyelembe vesszük, hogy a forrás olajmező, és hogy a kút az a finomító, ahol leeresztik, akkor a szelepeket úgy akarjuk beállítani, hogy a lehető legjobb áramlás legyen a forrásból a kútba. Más szavakkal, arra törekszünk, hogy az egyes élek kapacitását a lehető leghatékonyabban használják fel, ami a maximális áramlási probléma . Tegyük fel, hogy a grafikont két részre „vágjuk”, úgy, hogy az egyik a forrás, a másik pedig a mosogató. Minden áramnak át kell haladnia a két rész között, ezért korlátozza azt a maximális kapacitást, amelyet az egyik rész a másiknak küldhet. A legkisebb kapacitású vágás megkeresése tehát azt a helyet jelzi, ahol a hálózat a legkorlátozottabb, ami azt jelenti, hogy meghatározzuk azt a maximális áramlást, amely átmehet rajta. Ezt a tételt flow-max / cut-min- nek hívják, és 1956-ban hozták létre.
A hálózati áramlások tanulmányozása több szempontból is általános. A maximum keresése, itt az áramlás esetében, egy optimalizálási probléma , amely a matematika azon ága, amely egy függvény optimalizálásából ( azaz minimum vagy maximum megadása ) áll bizonyos korlátok mellett. A hálózati áramlásra három korlátozás vonatkozik: az egyes élek kapacitáskorlátja, a forrás és a mosogató között nem nulla áramlás létrehozása ( azaz a forrás áramot hoz létre), valamint a bemeneti / kimeneti áramlás egyenlősége bármely a forrástól és a mosogatóktól eltérő csúcs ( azaz nem fogyasztják és nem generálják az áramlás egy részét). Mivel ezek a korlátozások lineárisak , a hálózati áramlás problémája a lineáris optimalizálás része . Lehetőség van más változók hozzáadására is a problémához, hogy több helyzetet figyelembe vegyünk: így több forrásunk és süllyedőnk van (be) , az egyes éleken egy minimális kapacitás (be) , egy él használatakor költség vagy erősítés egy élen áthaladó áramlás (által) .
A XX . Század közepéig a grafikonalgoritmus felépítése nem volt véletlenszerű: mindaddig, amíg az algoritmus számára megadott paraméterek nem változtak, addig az általa épített grafikon ugyanaz volt. Ezután bevezettek egy bizonyos dózis véletlenszerűséget , és így az algoritmusok valószínűséggé váltak . Anatol Rapoport orosz származású matematikusnak ez az ötlete volt először 1957-ben, de két évvel később, formálisan, Erdős Paul és Rényi Alfréd magyar matematikusok önállóan javasolták . Arra voltak kíváncsiak, hogy néz ki egy „tipikus” gráf n csúcsú és m éllel. Azt akarták tudni, hogy mely tulajdonságok találhatók n csúcs és véletlenszerűen létrehozott m él mellett. Mivel egy fix m mennyiség nem célszerű megválaszolni ezt a kérdést, úgy döntöttünk, hogy minden él p valószínűséggel létezik . Ezzel kezdődött a véletlenszerű gráfok elmélete , ahol n csúcsszámot elég nagynak tekintünk, és érdekel bennünket az a p valószínűség, amely elegendő ahhoz, hogy a gráf egy bizonyos tulajdonsággal rendelkezzen.
Erdős és Rényi felfedezték, hogy a grafikon nem lineárisan fejlődött, ehelyett létezett egy kritikus p valószínűség, amely után radikálisan megváltozott. Ez a viselkedés jól ismert a fizikában: függetlenül attól, hogy van-e egy pohár víz, amelyet fagyasztóba tesznek , az fokozatosan nem vált jéggé, hirtelen, amikor a hőmérséklet 0 ° C alá esik . A víz volt két fázis (folyékony és jég), és halad az egyik a másik által nevezett jelenséggel fázis átmenet, az átmenet e gyors körül kritikus pont , amely ebben az esetben a hőmérséklet 0 ° C-on . Sok megfigyelt tulajdonság esetében a véletlenszerű grafikonok ugyanúgy működnek: van egy kritikus valószínűség , amely alatt szubkritikus fázisban vannak, és amely felett szuperkritikus fázisban mennek át. Véletlenszerű gráf esetén annak a valószínűsége, hogy megfigyeljük a számunkra érdekes tulajdonságot, a szubkritikus fázisban alacsony, de a túlkritikus fázisban nagyon magas ( azaz kvázibiztonság); A tulajdonság függvényének p függvényében való ábrázolása ezért nagyon sajátos megjelenésű, a jobb oldali ábrán egyszerűsítve.
A fázisok közös szókincsén túl a véletlenszerű grafikonok elmélete a statisztikai fizikában megtalálható a perkoláció elmélete formájában . Ez utóbbi eredetileg a folyadék porózus anyagon történő áramlásának vizsgálatát tűzte ki célul . Például, ha egy horzsakövet vízzel töltött vödörbe merítünk , akkor arra vagyunk kíváncsiak, hogy a víz hogyan fog folyni a kövön. A probléma modellezéséhez a fontos paraméterekre összpontosítunk: a kő kora vagy színe nem számít, míg a nyílások vagy a „csatornák”, amelyekben a víz keringhet, elengedhetetlenek. A legegyszerűbb absztrakció, ha egy követ rácsként tekintünk, ahol minden csatorna p valószínűséggel létezik . Megtaláljuk a véletlenszerű gráf modelljét, de térbeli kényszerrel : két csúcs között csak akkor létezhet él, ha szomszédosak a rácsban. Ez a korlát azonban megszüntethető, hogy ekvivalencia jöjjön létre a grafikonok elmélete és a perkoláció elmélete között. Először egy n csúcsú grafikon ábrázolható n dimenziós rács segítségével ; mivel érdekel bennünket az az eset, amikor n elég nagy, vagyis ez megalapozza a végtelen dimenzióban a perkolációval való egyenértékűséget. Ezenkívül létezik olyan kritikus dimenzió , hogy az eredmény már nem függ a dimenziótól, amint elérik ; úgy vélik, hogy ez a kritikus dimenzió 6, de csak 19 esetében bizonyítható.
A 2000-es évek eleje óta számos modellt javasoltak olyan grafikonokon megfigyelt jelenségek felkutatására, mint például a hollywoodi színészek közötti kapcsolatokat ábrázoló (az IMDb által megszerzett ) vagy a web egyes részei . 1999 -ben Barabási Albert-László és Albert Réka kifejtették, hogy e jelenségek egyike „két mechanizmus következménye: a hálózat új csúcsok hozzáadásával folyamatosan növekszik, és az új csúcsok bizonyos preferenciákkal kötődnek másokhoz, akik már jól vannak a helyén ". Bizonyos zavarodottság telepedett a modelljük körül: ha ez valóban lehetővé teszi a kívánt jelenség megszerzését, akkor nem ez az egyetlen modell érkezik ehhez az eredményhez, és ezért nem következtethetünk arra, hogy látjuk azt a jelenséget, amelyet egy preferenciális kötődési folyamat eredményez. A kis világ és a méretarányosság jelenségei , amelyekhez számos modellt javasoltak, egyszerűen véletlenszerű grafikonokkal érhetők el: Michael Molloy és Bruce Reed technikája lehetővé teszi a lépték nélküli, míg Li , Leonard és Loguinov a kis világba vezet.
Formálisan egy gráfot címkéznek : minden csúcs vagy él egy halmazhoz tartozik, ezért címkét visel . A grafikonokat általában egész számokkal jelölik, de egy címke tulajdonképpen bármely halmazhoz tartozhat: színkészlet, szavak halmaza, valós számok halmaza. A szemközti példák grafikonokat mutatnak egész számokkal és betűkkel. Címkézés gráf lehet célja, hogy hasznos információkkal ellátni problémák, mint routing : kezdve egy csúcsot , azt akarjuk, hogy egy olyan csúcs , vagyis azt akarjuk, hogy az útvonalat információkat az . A csúcsok címkézésének módjától függően azok a címkék, amelyek hordozzák és lehetővé teszik számunkra, hogy könnyen megtaláljuk a módját. Például a Kautz-gráfban (in), ahol a két csúcs közötti maximális távolság van , képzelje el, hogy egy címkézett csúcsnál vagyunk, és ahová szeretnénk menni : csak helyezze át a címkét a cél megadásával, ami utat enged
Ez az út a következőképpen szól: ha a címkézett tetején vagy, akkor a szomszédhoz lépsz a címkével stb.
Ugyanakkor egy problémával állunk szemben: ha a 2, 3 és 4 csúcsú fák listájának illusztrációja fölé nézünk, sokuknak pontosan ugyanaz a szerkezete, de más a címkéje (itt színek adják meg). Csak a szerkezet tanulmányozásához olyan eszközre van szükségünk, amely lehetővé teszi a címkézés figyelmen kívül hagyását, vagyis strukturális egyenértékűség biztosítását. Ehhez bevezetjük a morfizmus fogalmát. Egy gráf morfizmus , vagy gráf homomorfizmus , egy alkalmazás között két grafikon, amely tiszteletben szerkezetét grafikonok. Más szóval, a kép a grafikon a tiszteletben kell tartania a szomszédsági kapcsolatokban jelen . Pontosabban, ha a és két grafikon, egy alkalmazás egy morfizmus grafikonok, ha , ahol átalakítja a csúcsai G azokba a H, és a szélei G azokba a H tiszteletben tartása mellett a következő feltétel: ha van egy él két csúcsainak akkor kell legyen egy él a két megfelelő csúcsai . A homomorfizmusról azt mondjuk, hogy injekció (illetőleg szurjkció ), ha két funkciója és injektív (illetve szurjektív); ha egyszerre injektív és szurjektív, azaz bijektív , akkor a gráf izomorfizmus . Ha két gráf izomorf, akkor ugyanaz a felépítésük: függetlenül attól, hogy rajzolják-e vagy felcímkézik őket, lehetséges a csúcsok áthelyezése vagy a címkék megváltoztatása úgy, hogy az egyik szén másolata legyen a másiknak, amint az alább látható. Ezután jelöljük jelöletlen grafikon az ekvivalencia osztály egy grafikon az izomorfizmus kapcsolatban. Két izomorf gráfot ekkor tekintünk egyenlőnek, ha felirat nélküli gráfnak tekintjük őket.
G grafikon | H grafikon | Izomorfizmus G és H között |
---|---|---|
|
A grafikon szó a kontextustól függően jelölhet címkézett vagy címkézetlen grafikont. Amikor a webes grafikonról beszélünk, a címkék URL-ek és jelentéssel bírnak. A szó címkézett gráf jelölésére szolgál. Ezzel szemben a Petersen-gráf mindig az izomorfizmusig tekinthető, ezért címkézetlen, csak annak szerkezeti tulajdonságai érdekesek.
Az ábécén feliratozott hiperkocka
Egész számokkal címkézett grafikon
Betűkkel ellátott grafikon
Bármely gráf ábrázolható mátrixszal . Az élek és csúcsok közötti kapcsolatokat, az úgynevezett incidencia összefüggéseket, mind a gráf incidencia mátrixa képviseli . A szomszédságok viszonyait (ha két csúcsot összeköt egy él, amelyek szomszédosak) a szomszédsági mátrix képviseli . Meghatározza
Grafikon | A szomszédsági mátrix ábrázolása | Laplaciánus mátrix ábrázolása (nem normalizált) |
---|---|---|
A gráfban található sok információt egy mátrix képviselheti. Például a fokok mátrixa egy átlós mátrix, ahol az elemek megfelelnek a csúcs kapcsolatainak számának , vagyis annak fokának . Ezen és az előző felhasználásával meghatározhatjuk a Laplac-féle mátrixot is ; normalizált formáját azáltal kapjuk meg , ahol az identitásmátrixot jelöli , vagy közvetlenül megkaphatjuk az egyes elemei által is:
Ezek az ábrázolások a grafikon csúcsainak címkézésétől függenek. Képzeljük el, hogy ugyanazt a struktúrát tartjuk fenn, mint a fenti példában, és hogy megfordítjuk az 1. és 6. címkét : ezután visszafordítjuk a szomszédsági mátrix 1. és 6. oszlopát . Vannak azonban olyan mennyiségek, amelyek nem függenek a csúcsok címkézésének módjától, például a gráf minimális / maximális / átlagos foka. Ezek a mennyiségek a gráf invariánsai : a számozás szerint nem változnak. Míg egy szomszédsági vagy laplaci mátrix változó, spektruma , vagyis sajátértékeinek halmaza invariáns. A spektrumok és a grafikon tulajdonságai közötti kapcsolat vizsgálata a spektrális gráfelmélet tárgya ; az érdekes arányok között a spektrum információt ad a kromatikus számról , a csatlakoztatott komponensek számáról és a grafikon ciklusairól.
Mivel a grafikonok sok helyzetet képesek ábrázolni, sok algoritmus ( azaz program) használja ezeket. Az algoritmus bonyolultsága lényegében abból áll, hogy egy adott probléma esetén tudjuk, mennyi időre van szükség a megoldáshoz, és mekkora gépteret fog használni. Egyes grafikonos ábrázolások jobb teljesítményt nyújtanak, vagyis a probléma gyorsabban megoldódik vagy kevesebb helyet foglal el. Bizonyos esetekben egy NP-teljes probléma (a legnehezebb osztály) egy gráf ábrázolásán polinomiális időben (egyszerű osztály) megoldható egy másik ábrázolással; az ötlet nem az, hogy a probléma gyorsabb megoldásához elegendő a grafikont másképp nézni, hanem az, hogy az ember "fizet" az átalakításáért, és hogy azután "ment" a probléma megoldására. Az egyik ilyen átalakítás a fák lebontása, amelyet Robertson és Seymour matematikusok javasoltak a Graph Minors sorozatukban . Intuitív módon egy fa felbontása egy fa által ábrázolja az eredeti gráfot , ahol minden csúcs a G csúcsainak egy részhalmazának felel meg, bizonyos korlátozásokkal. Formálisan egy adott gráf esetében a fa lebontása az, ahol egy fa és egy függvény az egyes csúcsokhoz csúcsok halmazát társítja . Három feltételnek kell teljesülnie:
A fa szélessége A bomlás egy gráf van , azaz a méret a legnagyobb szettet képviseli vertex mínusz 1; a maximális absztrakciónak tekinthetjük: a fa tetejénél a gráf hány csúcsáig képviselünk? Bármely, a legkisebb faszélességű gráf fa lebontásának felépítése NP-nehéz probléma. Ez azonban egyes grafikonok esetében gyorsan elvégezhető, mások esetében pedig közelítéssel, például sík gráfokkal ( azaz két él keresztezése nélkül is megrajzolható).
Robertson és Seymour kidolgozta az elágazás koncepcióját is . Ahhoz, hogy megértse, több szókincset kell bevezetnie egy fába. A grafikonokban egy fa "fejjel lefelé" van rajzolva: a gyökérből indulunk ki a tetején, és leereszkedünk, amíg el nem érjük az alján levő leveleket; minden csúcsot, amely nem levél, „belső csomópontnak” nevezzük. Az ágakra bomlás egy olyan fát eredményez, amelyben minden belső csomópontnak pontosan három szomszédja van (mint a szemközti példában), és ahol minden levél az eredeti gráf szélét képviseli. Megjegyezzük a gráf lebontásának minimális mélységét , és megvan a kapcsolat . Ami a fa lebontását illeti, NP-nél nehéz olyan ágbontást megalkotni, amely bármelyik grafikonra minimális; ebben az esetben ez a konstrukció megvalósítható egy sík gráfnál .
Ezeket a reprezentációkat az NP-teljes problémákra használják dinamikus programozási technikák , amelyek általában exponenciális időt vesznek igénybe a vagy a-ban . Ilyen probléma például a domináns halmaz : szeretnénk tudni, hogy van-e legfeljebb olyan méretű csúcsok részhalmaza , hogy az y-ben nem levő csúcsot egy él köti össze. Ha a grafikon sík, ez a technika lehetővé teszi a probléma időben történő megoldását .
A grafikon matematikai objektumként való megjelenítésének módjáról az előző szakasz foglalkozott. A gráfelmélet algoritmikus aspektusában arra törekszünk, hogy hatékony folyamatot tervezzünk egy gráfot érintő probléma kezelésére. A folyamat hatékonyságának fő kritériuma a válasz megszerzéséhez szükséges idő, valamint a folyamat munkájában elfogyasztott hely. A grafikon ábrázolásának módja befolyásolja az időbeli és térbeli teljesítményt: ha például meg akarjuk ismerni egy él létezését két csúcs között, akkor a szomszédsági mátrix lehetővé teszi az azonnali eredmény elérését, ezt hívjuk ben . Másrészt egy olyan alapművelet, mint például egy csúcs szomszédjának megkeresése , egy szomszédsági mátrixon található: legrosszabb esetben az egész oszlopot át kell vizsgálni, hogy kiderüljön, nincs szomszéd. Egy másik adatszerkezet a szomszédsági lista , amely egy tömbből áll, amelynek bejegyzésével megadjuk a csúcs szomszédjainak listáját : egy ilyen struktúrán a szomszéd megtalálása akkor történik, amikor egy él létezik . Így az idő szempontjából a struktúra megválasztása az optimális műveletektől függ.
A szemközti grafikon szomszédsági listája szerinti ábrázolás: | ||
0 | szomszédos | 0,1,2,3 |
1 | szomszédos | 0 |
2 | szomszédos | 0.3.4 |
3 | szomszédos | 0.2 |
4 | szomszédos | 2 |
Hasonlóképpen, az a terület, amelyet egy szerkezet elfogyaszt, a figyelembe vett gráf típusától függ: egy visszaélő parancsikon abból áll, hogy a szomszédságok listája kevesebb helyet foglal el, mint egy mátrix, mert ez utóbbi ritka lesz , de ez például több helyet igényel egy véletlenszerű grafikon a listákkal, mint egy mátrixszal; általános esetben egy mátrix teret használ, és ezért a felsorolásokat használja, ha a grafikon sűrű, akkor elég nagy lehet ahhoz, hogy egy mátrix kevesebb helyet használjon fel, és ha a gráf ritka, akkor a listák kevesebb helyet foglalnak el. Az adatszerkezet egyszerű módosítása lehetővé teszi az érezhető nyereség elérését: például egy lista részben kiegészített ábrázolásakor egy speciális bit jelzi, hogy a lista a jelen lévő szomszédoké vagy hiányzik-e; ez a technika lehetővé teszi, hogy lineáris algoritmusok legyenek a gráf kiegészítésén.
Bár ezek a struktúrák lokálisak, vannak elosztott adatstruktúrák is . Az elv ezeket a struktúrákat, hogy tervezzen egy címkézési rendszer olyan, hogy két csúcs és , lehet válaszolni a kérdésre, hogy „mi a távolság és a ” csak használja a címkéket ezen csomópontok; a címkék ilyen használatát a Kautz-gráf „ Címkézés és morfizmusok ” szakaszában láthattuk, ahol csak a címkéjüknek köszönhetően következtethetünk két csúcs közötti útra, és ennek az útnak a hossza adja meg a távolságot. A címkézés akkor hatékony, ha az adott kérdésre csak két címke használatával ad választ, miközben minimalizálja a címke maximális bitszámát. A távolság mellett tipikus kérdés lehet a szomszédság tesztelése, vagyis tudni kell, hogy két csúcs közel van-e; vegye figyelembe, hogy ez az 1. távolság speciális esetére is visszavezethető. A szomszédság tesztelésére szolgáló hatékony címkézés első példáját a fák esetében javasolták, és mindegyik címke két részből áll : az első a csúcsot azonosítja, és egy számig bitek kódolása szükséges , míg a második rész a csúcs szülőjét azonosítja; a szomszédság teszteléséhez azt a tényt használjuk, hogy két csúcs akkor és csak akkor szomszédos a fán, ha az egyik a másik szülője.
A címkézési séma hatékonysága összefügg a grafikonon levő elválasztók méretével.
Definíció - egy elválasztó egy részhalmaza csúcsok, hogy „split” a csúcsai a gráf két komponensre , és olyan, hogy , és nincsenek élei között csúcsai és a .
Ha egy grafikon méretelválasztóval rendelkezik , akkor például tervezhetünk bitcímkéket a távolsághoz; ez közvetlenül lehetővé teszi azoknak a grafikonoknak a jelölését, amelyeknél az elválasztók mérete ismert, például egy síkbeli gráfnál, ahol az elválasztó méretben van . Végül nem csak a címkézés méretét kell figyelembe vennünk, hanem azt a időt is, amely két címke esetén a dekódolás elvégzéséhez szükséges a kérdés megválaszolásához ( azaz mekkora a távolság? Szomszédok?).
Számos gráfprobléma NP-hiányos, vagyis nehezen megoldható. Ez a durvaság azonban egyenetlen: a probléma egyes részei különösen kemények lehetnek, és így jelenthetik annak alapját, míg másokkal meglehetősen könnyű kezelni. Tehát, mielőtt algoritmust futtatna egy nehéz problémára, a legjobb, ha egy kis időt tölt el a probléma csökkentésével, hogy csak a magját kell figyelembe vennie.