Hranový graf

V teorii grafů je spojnicový graf L ( G ) neorientovaného grafu G grafem L ( G ) reprezentujícím okolí hran grafu G .

Pojem spojnicový graf pro daný graf je natolik přirozený, že jej nezávisle na sobě zavedlo mnoho autorů. Každý z nich si samozřejmě dal své jméno: Ore [1] nazval tento graf "graf sousednosti" , Sabidussi [2] - "odvozený graf" , Beinecke [3] - "odvozený graf" , Sechu a Read [4] - "edge -vertex-dual" , Castelein [5] - "krycí graf" , Menon [6] - "adjoint" ("adjoint") [7] [8] [9] .

Jednu z nejstarších a nejdůležitějších vět o spojnicovém grafu má na svědomí Whitney, který dokázal, že až na jednu výjimku je struktura grafu G zcela definována spojnicovým grafem. Jinými slovy, až na jednu výjimku lze celý graf rekonstruovat ze spojnicového grafu.

Formální definice

Nechť je dán graf G , pak jeho spojnicový graf L ( G ) je graf takový, že

Příklady

Příklad stavby

Následující obrázek ukazuje graf (vlevo s modrými vrcholy) a jeho spojnicový graf (vpravo se zelenými vrcholy). Každý vrchol spojnicového grafu je označen dvojicí čísel vrcholů odpovídající hrany v původním grafu. Například zelený vrchol vpravo označený 1,3 odpovídá hraně vlevo mezi modrými vrcholy 1 a 3. Zelený vrchol 1,3 sousedí s dalšími třemi zelenými vrcholy: 1,4, 1,2 ( odpovídající hranám, které sdílejí vrchol 1 v modrém grafu, a 4,3 (odpovídající hranám se společným vrcholem 3 v modrém grafu).

Chordálové grafy

Spojnicový graf úplného grafu K n je známý jako chordální graf (nebo triangulovaný graf ). Důležitou větou o akordických grafech je věta, která říká, že akordický graf je charakterizován spektrem , kromě n = 8, kdy existují tři další grafy se stejným spektrem jako L ( K 8 ). Výjimky jsou vysvětleny v Přepínání grafů .

Spojnicové grafy konvexních mnohostěnů

Zdroj příkladů spojnicových grafů lze nalézt v geometrii - pro grafy jednoduchých polytopů . Pokud sestavíme spojnicový graf pro čtyřstěnný graf , dostaneme osmistěnný graf . Z grafu krychle dostaneme graf kuboktaedru . Z grafu dvanáctistěnu získáme graf ikosidodekaedru atd. Geometricky operace spočívá v odříznutí všech vrcholů mnohostěnu rovinou protínající všechny hrany sdružené s vrcholem v jejich středu.

Pokud mnohostěn není jednoduchý (to znamená, že má více než tři plochy na vrchol), čárový graf nebude rovinný.

Mediánový graf

Mediánový graf je variantou spojnicového grafu pro rovinný graf. Ve středním grafu sousedí dva vrcholy právě tehdy, když odpovídající hrany původního grafu jsou dvě po sobě jdoucí hrany nějaké oblasti rovinného grafu. Pro jednoduché polygony jsou střední graf a spojnicový graf stejné, ale u složitých mnohoúhelníků zůstává mediánový graf plochý. Střední grafy krychle a osmistěnu jsou tedy izomorfní ke grafu koboktaedru a střední grafy dvanáctistěnu a dvacetistěnu jsou izomorfní ke grafu ikosidodekaedru.

Vlastnosti

Vlastnosti grafu G závislé pouze na sousednosti hran lze převést na ekvivalentní vlastnosti grafu L ( G ), které závisí pouze na sousednosti vrcholů. Například shoda v G  je množina oblouků, z nichž žádný nesousedí s druhým, a odpovídající množina vrcholů v L ( G ), z nichž žádný nesousedí s druhým, tedy nezávislá množina vrcholy .

Tak,

Protože maximální shodu lze nalézt v polynomiálním čase, lze maximální nezávislou množinu spojnicového grafu nalézt také v polynomiálním čase, a to navzdory obtížnosti nalezení takové množiny pro obecnější rodiny grafů.

Charakteristiky a rozpoznávání

Graf G je spojnicový graf nějakého jiného grafu právě tehdy, když je možné najít množinu klik v G , které rozdělují oblouky G takovým způsobem, že každý vrchol G patří právě dvěma klikám. Může se stát, že aby toho bylo dosaženo, je nutné vybrat jednotlivé vrcholy v klikech. Podle Whitneyho věty  [10] [11] , pokud G není trojúhelník, může existovat pouze jeden oddíl tohoto druhu. Pokud existuje oddíl, můžeme sestrojit graf, pro který G je spojnicový graf, a to vytvořením vrcholu pro každou kliku a spojením výsledných vrcholů hranou, pokud vrchol patří oběma klikám. Tedy, s výjimkou a , jestliže dva spojnicové grafy spojených grafů jsou izomorfní k , pak jsou grafy také izomorfní. Roussopoulos [12] použil toto pozorování jako základ pro časově lineární algoritmus pro rozpoznávání spojnicových grafů a rekonstrukci jejich původních grafů.

Takovou charakteristiku lze například použít k ukázce, že následující graf není spojnicový:

V tomto příkladu hrany směřující od centrálního vrcholu 4. stupně nahoru, doleva a doprava neobsahují společné kliky. Jakékoli rozdělení hran grafu na kliky tedy musí obsahovat alespoň jednu kliku pro každou z těchto tří hran a všechny tři kliky se protínají v centrálním vrcholu, což porušuje podmínku, že každý vrchol patří právě dvěma klikám. Zobrazený graf tedy nemůže být spojnicový graf.

Další charakteristiku grafu dokázal Beinecke [13] (a bez důkazu ji již dříve zmínil [3] ). Ukázal, že existuje devět minimálních nečárových grafů, takže každý nečárový graf obsahuje jeden z těchto devíti grafů jako vygenerovaný podgraf . Graf je tedy spojnicovým grafem právě tehdy, když žádná podmnožina vrcholů negeneruje jeden z těchto devíti. Ve výše uvedeném příkladu generují čtyři horní vrcholy dráp (tj. úplný bipartitní graf K 1,3 ), znázorněný v levé horní části ilustrace zakázaného podgrafu. Podle Beineckeovy charakteristiky tedy tento graf nemůže být spojnicovým grafem. Pro grafy s vrcholovým stupněm alespoň 5 lze grafem vygenerovat pouze šest podgrafů v levém a pravém sloupci obrázku [14] . Tento výsledek je podobný výsledku pro hypergrafické spojnicové grafy [15] .

Opakování operace sestrojení spojnicového grafu

Ruij a Wilf [16] uvažovali o posloupnosti grafů

Ukázali, že pro konečný graf souvislého grafu G jsou možná pouze čtyři chování této posloupnosti:

Pokud je G odpojeno, pak tato klasifikace platí pro každou jednotlivou připojenou součást G .

Vztah k jiným skupinám grafů

Žádný spojnicový graf neobsahuje drápy .

Spojnicový graf bipartitního grafu je dokonalý (viz Königova věta ). Spojnicové grafy bipartitních grafů tvoří jeden z klíčových stavebních kamenů, který se používá k prokázání věty o dokonalém grafu. Speciálním případem jsou věžové grafy , spojnicové grafy úplných bipartitních grafů .

Zobecnění

Multigrafy

Koncept spojnicového grafu pro graf G lze přirozeně rozšířit na případ, kdy G je multigraf, i když v tomto případě Whitneyova věta o jedinečnosti ztrácí platnost. Například úplný bipartitní graf K 1, n má stejný spojnicový graf jako dipólový graf a Shannonův multigraf se stejným počtem hran.

Okrajové digrafy

Spojnicové grafy lze také zobecnit na orientované grafy [17] . Je-li G  orientovaný graf, pak jeho orientovaný spojnicový graf nebo spojnicový digraf má jeden vrchol pro každý oblouk v G . Dva vrcholy odpovídající obloukům od u do v a od w do x z grafu G jsou spojeny obloukem od uv do wx v liniovém digrafu, když v = w . Každý oblouk v liniovém digrafu tedy odpovídá dráze délky 2 v původním grafu. De Bruijnovy grafy lze získat opakovaným sestavováním orientovaných liniových grafů, počínaje úplným digrafem [18] .

Vážené spojnicové grafy

Každý vrchol stupně k v původním grafu G vytváří k(k-1)/2 hran v liniovém grafu L ( G ). Pro mnoho druhů analýz to znamená, že vrcholy vysokých stupňů v G jsou v liniovém grafu L ( G ) zastoupeny silněji . Představte si například náhodnou procházku po vrcholech původního grafu G . Projdeme podél hrany e s určitou pravděpodobností f . Na druhé straně hrana e odpovídá jedinému vrcholu, řekněme v , v liniovém grafu L ( G ). Pokud nyní provedeme stejný typ náhodné procházky přes vrcholy spojnicového grafu, frekvence návštěv v se může ukázat jako zcela odlišná od f . Pokud by naše hrana e v G byla spojena s vrcholy stupně O(k) , procházela by se v liniovém grafu L ( G ) častěji O(k 2 ) . Whitneyův teorém [10] tedy zaručuje, že spojnicový graf téměř vždy obsahuje zakódovanou topologii G , nezaručuje, že oba grafy mají jednoduché dynamické souvislosti. Jedním z řešení tohoto problému je vytvořit vážený spojnicový graf, tedy spojnicový graf, jehož hrany jsou zváženy. Existuje několik přirozených způsobů, jak toho dosáhnout [19] . Pokud jsou například hrany d a e v grafu G sdružené ve vrcholu v stupně k , pak v liniovém grafu L ( G ) lze hraně spojující dva vrcholy d a e přiřadit váhu 1/(k- 1) . Stejně tak jakákoli hrana v G (pokud není spojena s vrcholem stupně 1 ) bude mít v liniovém grafu L ( G ) váhu 2 , odpovídající dvěma koncům hrany v G .

Spojnicové grafy hypergrafů

Hrany hypergrafu mohou tvořit libovolnou rodinu množin, takže spojnicový graf hypergrafu  je stejný jako průsečík množin rodiny.

Poznámky

  1. ↑ O. Rud. Hamilton spojené grafy // J. Math. Pures Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Grafy s danou skupinou a danými praph-teoretickými vlastnostmi  // Kanad. J Math. - 1957. - T. 9 . - S. 515-525 .
  3. ↑ 1 2 L. W. Beineke. Beitrage zur Graphentheorie. — Lipsko: Teubner, 1968.
  4. ↑ Seshu S., Reed M. Lineární grafy a elektrické obvody. - M . : Vyšší škola, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. Rozpustný problém s vyhýbáním se chůzi // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. O opakovaných výměnných grafech // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Graph Theory = Graph Theory / Překlad z angličtiny a předmluva V.P. Kozyrev. - 2. - M. : Editorial URSS, 2003. - 296 s.
  8. ↑ Nástin teorie grafů Balakrishnana VK Schauma. — 1. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R. L. Hemminger, L. W. Beineke. Vybraná témata z teorie grafů. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Kongruentní grafy a konektivita grafů  // American Journal of Mathematics. - 1932. - T. 54 , čís. 1 . - S. 150-168 . - doi : 10.2307/2371086 . — .
  11. ↑ J. Krausz. 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. Algoritmus max { m , n } pro určení grafu H z jeho spojnicového grafu G  // Information Processing Letters. - 1973. - Vol. 2 , vydání. 4 . - S. 108-112 . - doi : 10.1016/0020-0190(73)90029-X .
  13. ↑ LW Beineke. Charakterizace odvozených grafů // Journal of Combinatorial Theory. - 1970. - Sv. 9. - S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Yury Metelsky, Regina Tyshkevich. On line grafy lineárních 3-uniformních hypergrafů // Journal of Graph Theory. - 1997. - T. 25 , no. 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  na webu Wolfram MathWorld .
  16. ↑ ACM van Rooij, H. S. Wilf. Výměnný graf konečného grafu // Acta Mathematica Hungarica. - 1965. - T. 16 , čís. 3-4 . - S. 263-269 . - doi : 10.1007/BF01904834 .
  17. ↑ Frank Harary, RZ Norman. Některé vlastnosti liniových digrafů // Rendiconti del Circolo Matematico di Palermo . - 1960. - T. 9 , čís. 2 . - S. 161-169 . - doi : 10.1007/BF02854581 .
  18. ↑ Fu Ji Zhang, Guo Ning Lin. Na grafech de Bruijn–Good // Acta Math. Sinica. - 1987. - T. 30 , no. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Spojnicové grafy, odkazové oddíly a překrývající se komunity // Phys.Rev.E. - 2009. - T. 80 . - doi : 10.1103/PhysRevE.80.016105 .

Odkazy