Vonal grafikon

A gráfelméletben egy irányítatlan G gráf L ( G ) vonalgráfja a G gráf éleinek szomszédságát reprezentáló L ( G ) gráf .

A vonalgráf fogalma egy adott gráfra annyira természetes, hogy számos szerző önállóan bevezette. Természetesen mindegyikük saját nevet adott: Ore [1] ezt a gráfot "szomszédsági gráfnak" nevezte , Sabidussi [2] - "derivatív gráf" , Beinecke [3] - "derivált gráf" , Sechu és Read [4] - "edge -vertex-dual" , Castelein [5] - "fedő gráf" , Menon [6] - "adjoint" ("adjungált") [7] [8] [9] .

Az egyik legkorábbi és legfontosabb vonalgráf-tétel Whitney-nek köszönhető, aki bebizonyította, hogy a G gráf szerkezetét egy kivétellel teljesen egy vonalgráf határozza meg. Más szóval, egy kivétellel a teljes gráf rekonstruálható a vonalgráfból.

Formális definíció

Legyen adott egy G gráf , akkor annak L ( G ) vonalgráfja olyan gráf, amelyre

Példák

Építési példa

A következő ábra egy gráfot (bal oldalon, kék csúcsokkal) és annak vonalgráfját (jobb oldalon, zöld csúcsokkal) mutatja. A vonalgráf minden csúcsa az eredeti gráf megfelelő élének csúcsszám-párjával van felcímkézve. Például a jobb oldali, 1,3-mal jelölt zöld csúcs megfelel a bal oldali, az 1 és 3 kék csúcsok közötti élnek. Az 1,3 zöld csúcs három másik zöld csúcs szomszédságában van: 1,4, 1,2 ( megfelel a kék gráf 1-es csúcsával rendelkező éleknek, és 4,3 (a kék gráf 3-as közös csúcsával rendelkező éleknek felel meg).

Akkordgráfok

A K n teljes gráf vonalgráfja akkordgráfként (vagy háromszögelt gráfként ) ismert . Az akkordgráfokkal kapcsolatos fontos tétel az a tétel, amely kimondja, hogy egy akkordgráfot spektrum jellemzi , kivéve n = 8 esetén, amikor három másik gráf is azonos spektrummal rendelkezik L -vel ( K8 ). A kivételeket a Grafikonváltás című rész ismerteti .

Konvex poliéderek vonalgráfjai

A vonalgráfok példáinak forrása a geometria - egyszerű politópok gráfjaihoz című részben található . Ha egy tetraéder gráfhoz készítünk vonalgráfot , akkor egy oktaéder gráfot kapunk . A kocka grafikonjából megkapjuk a kockaéder grafikonját . A dodekaéder gráfjából megkapjuk az ikozidodekaéder gráfját , és így tovább. Geometriailag a művelet abból áll, hogy a poliéder összes csúcsát levágjuk egy síkkal, amely metszi a közepén lévő csúcshoz konjugált összes élt.

Ha a poliéder nem egyszerű (vagyis csúcsonként háromnál több lapja van), akkor a vonalgráf nem lesz síkbeli.

Medián gráf

A medián gráf a sík gráf vonalgráfjának egy változata. Egy középső gráfban két csúcs akkor és csak akkor szomszédos, ha az eredeti gráf megfelelő élei a síkgráf valamely területének két egymást követő élei. Egyszerű sokszögeknél a medián gráf és a vonalgráf ugyanaz, de összetett sokszögeknél a medián gráf lapos marad. Így egy kocka és egy oktaéder középső gráfja izomorf egy kuboktaéder gráfjával, a dodekaéder és egy ikozaéder középső gráfja pedig egy ikozidodekaéder gráfjával.

Tulajdonságok

A G gráf azon tulajdonságai, amelyek csak az élek szomszédságától függenek, lefordíthatók az L ( G ) gráf ekvivalens tulajdonságaira, amelyek csak a csúcsok szomszédságától függenek. Például egy G -beli illeszkedés olyan  ívek halmaza, amelyek egyike sem szomszédos a másikkal, és egy megfelelő csúcshalmaz L -ben ( G ), amelyek egyike sem szomszédos a másikkal, azaz egy független halmaz csúcsok .

Így,

Mivel a maximális illeszkedés polinomidőben található, a vonalgráf maximális független halmaza is megtalálható polinomiális időben, annak ellenére, hogy az általánosabb gráfcsaládok esetében nehéz ilyen halmazt találni.

Jellemzők és felismerés

A G gráf egy másik gráf vonalgráfja akkor és csak akkor, ha G-ben találhatunk olyan klikkeket , amelyek G íveit úgy hasítják fel, hogy G minden csúcsa pontosan két klikkhez tartozik. Előfordulhat, hogy ennek eléréséhez a klikkekben egyedi csúcsokat kell kiválasztani. Whitney [10] [11] tétele szerint , ha G nem háromszög, csak egy ilyen partíció létezhet. Ha létezik partíció, akkor létrehozhatunk egy gráfot, amelynek G vonalgráfja úgy, hogy minden klikkhez létrehozunk egy csúcsot, és az így kapott csúcsokat összekötjük egy éllel, ha a csúcs mindkét klikkhez tartozik. Így a és kivételével , ha két összefüggő gráf vonalgráfja izomorf -vel , akkor a gráfok is izomorfak. Roussopoulos [12] ezt a megfigyelést használta egy idő-lineáris algoritmus alapjául a vonalgráfok felismerésére és eredeti gráfjaik rekonstruálására.  

Egy ilyen karakterisztikával például meg lehet mutatni, hogy a következő grafikon nem vonaldiagram:

Ebben a példában a 4. fok középső csúcsától felfelé, balra és jobbra tartó élek nem tartalmaznak közös klikkeket. Tehát a gráf éleinek klikkekre való felosztásának tartalmaznia kell legalább egy klikket mindhárom élhez, és mindhárom klikk a központi csúcsban metszi egymást, ami sérti azt a feltételt, hogy minden csúcs pontosan két klikkhez tartozik. Így a bemutatott grafikon nem lehet vonalgráf.

A gráf másik jellemzőjét Beinecke [13] bizonyította (és korábban bizonyítás nélkül említette [3] ). Megmutatta, hogy kilenc minimális nem-vonalas gráf létezik, így bármely nem-vonalas gráf a kilenc gráf egyikét tartalmazza generált részgráfként . Így egy gráf akkor és csak akkor vonalgráf, ha a csúcsok egyik részhalmaza sem generál e kilenc közül egyet sem. A fenti példában a felső négy csúcs egy karmot (vagyis egy teljes kétrészes gráfot K 1,3 ) generál, amely a tiltott részgráf illusztrációjának bal felső sarkában látható. Így a Beinecke-karakterisztika szerint ez a gráf nem lehet vonalgráf. A legalább 5-ös csúcsfokú gráfoknál az ábra bal és jobb oszlopában csak hat részgráf állítható elő a gráf segítségével [14] . Ez az eredmény hasonló a hipergráf vonalgráfok eredményéhez [15] .

Egy vonalgráf szerkesztési műveletének megismétlése

Ruij és Wilf [16] a gráfok sorozatát vizsgálta

Megmutatták, hogy egy G összefüggő gráf véges gráfjához ennek a sorozatnak csak négy viselkedése lehetséges:

Ha G szét van kötve, akkor ez a besorolás G minden egyes csatlakoztatott összetevőjére vonatkozik .

Kapcsolat más gráfcsaládokkal

Egyik vonaldiagram sem tartalmaz karmokat .

Egy kétrészes gráf vonalgráfja tökéletes ( lásd König tételét ). A kétrészes gráfok vonalgráfjai alkotják az egyik kulcsfontosságú építőelemet, amelyet a tökéletes gráftétel bizonyítására használnak. Speciális eset a bástyagráfok , a teljes kétrészes gráfok vonalgráfjai .

Általánosítások

Multigráfok

A vonalgráf fogalma egy G gráfra természetesen kiterjeszthető arra az esetre, amikor G multigráf, bár ebben az esetben Whitney egyediségtétele érvénytelenné válik. Például a K 1, n teljes kétrészes gráfnak ugyanaz a vonalgráfja, mint a dipólusgráfnak és a Shannon-multigráfnak , ugyanannyi éllel.

Éldigráfok

A vonalgráfokat irányított gráfokra is általánosíthatjuk [17] . Ha G  egy irányított gráf, akkor az irányított vonalgráfjának vagy kétvonalas digráfjának van egy csúcsa G minden ívéhez . A G gráf u -tól v -ig és w -től x -ig tartó íveinek megfelelő két csúcsot egy uv -ból wx -be húzó ív köt össze egy egyenes digráfban, ha v = w . Így a vonaldigráf minden íve megfelel egy 2 hosszúságú útnak az eredeti gráfban. A De Bruijn-gráfokat úgy kaphatjuk meg, hogy ismételt irányított vonalgráfokat készítünk, egy teljes digráftól kezdve [18] .

Súlyozott vonaldiagramok

Az eredeti G gráf minden k fokú csúcsa k(k-1)/2 élt hoz létre az L vonalgráfban ( G ). Sokféle elemzésnél ez azt jelenti, hogy a G -beli magas fokú csúcsok erősebben jelennek meg az L vonalgráfban ( G ). Képzeljünk el például egy véletlenszerű sétát az eredeti G gráf csúcsai felett . Némi f valószínűséggel haladunk végig az e élen . Másrészt az e él egyetlen csúcsnak felel meg, mondjuk v , az L ( G ) vonalgráfban. Ha most ugyanazt a véletlenszerű sétát hajtjuk végre egy vonalgráf csúcsain, akkor a v látogatási gyakoriság egészen másnak bizonyulhat, mint az f . Ha a G - beli e élünk O(k) fokú csúcsokhoz kapcsolódna , akkor az L ( G ) vonalgráfban O(k 2 ) gyakrabban járna be . Így bár Whitney tétele [10] garantálja, hogy egy vonalgráf szinte mindig tartalmazza G kódolt topológiáját , nem garantálja, hogy a két gráfnak egyszerű dinamikus kapcsolatai vannak. Ennek a problémának az egyik megoldása egy súlyozott vonalgráf létrehozása, azaz egy olyan vonalgráf, amelynek élei súlyozottak. Ennek számos természetes módja van [19] . Például, ha egy G gráfban d és e élek konjugáltak egy k fokú v csúcsban , akkor egy L ( G ) vonalgráfban a két d és e csúcsot összekötő élhez 1/(k-) súlyt rendelhetünk . 1) . Ugyanígy minden G -beli élnek (kivéve, ha 1 fokú csúcshoz kapcsolódik ) 2 lesz a súlya az L ( G ) vonalgráfban, ami megfelel a G -beli él két végének .

Hipergráfok vonaldiagramjai

A hipergráf élei bármilyen halmazcsaládot alkothatnak, ezért a hipergráf vonalgráfja megegyezik  egy család halmazainak metszésgráfjával.

Jegyzetek

  1. ↑ O. Érc. Hamilton összekapcsolt gráfok // J. Math. Pures Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Grafikonok adott csoporttal és adott praph-elméleti tulajdonságokkal  // Canad. J Math. - 1957. - T. 9 . - S. 515-525 .
  3. ↑ 1 2 L. W. Beineke. Beitrage zur Graphentheorie. – Lipcse: Teubner, 1968.
  4. ↑ Seshu S., Reed M. Lineáris gráfok és elektromos áramkörök. - M . : Felsőiskola, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. Egy oldható önelkerülő gyaloglási probléma // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. Ismételt interchange grafikonokon // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Graph Theory = Graph Theory / Fordítás angolból és előszó V.P. Kozyrev. - 2. - M. : Szerkesztői URSS, 2003. - 296 p.
  8. ↑ Balakrishnan VK Schaum gráfelmélet vázlata. — 1. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R. L. Hemminger, L. W. Beineke. A gráfelmélet válogatott témái. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Egybevágó gráfok és a gráfok összekapcsolhatósága  // American Journal of Mathematics. - 1932. - T. 54 , sz. 1 . - S. 150-168 . - doi : 10.2307/2371086 . — .
  11. ↑ Krausz J.. Demonstration nouvelle d'un théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. - 1943. - T. 50 . - S. 75-85 .
  12. ↑ N.D. Roussopoulos. Egy max { m , n } algoritmus a H gráf meghatározására annak G  vonalgráfjából // Információfeldolgozási betűk. - 1973. - 2. kötet , szám. 4 . - S. 108-112 . - doi : 10.1016/0020-0190(73)90029-X .
  13. ↑ LW Beineke. Levezetett gráfok jellemzése // Journal of Combinatorial Theory. - 1970. - 1. évf. 9. - S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Jurij Metelszkij, Regina Tyskevich. Lineáris 3-uniform hipergráfok vonalgráfjai // Journal of Graph Theory. - 1997. - T. 25 , sz. 4 . - S. 243-251 . - doi : 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  15. ↑ Weisstein, Eric W. Line Graph  a Wolfram MathWorld webhelyen .
  16. ↑ ACM van Rooij, H. S. Wilf. Egy véges gráf cseregráfja // Acta Mathematica Hungarica. - 1965. - T. 16 , sz. 3-4 . - S. 263-269 . - doi : 10.1007/BF01904834 .
  17. ↑ Frank Harary, RZ Norman. A vonaldigráfok néhány tulajdonsága // Rendiconti del Circolo Matematico di Palermo . - 1960. - T. 9 , sz. 2 . - S. 161-169 . - doi : 10.1007/BF02854581 .
  18. ↑ Fu Ji Zhang, Guo Ning Lin. A de Bruijn–Jó grafikonokon // Acta Math. Sinica. - 1987. - T. 30 , sz. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Vonalgrafikonok, linkpartíciók és átfedő közösségek // Phys.Rev.E. - 2009. - T. 80 . - doi : 10.1103/PhysRevE.80.016105 .

Linkek