Hranový graf - Line graph
V matematický disciplína teorie grafů, hranový graf z neorientovaný graf G je další graf L (G), který představuje sousedství mezi hrany z G. L (G) je konstruován následujícím způsobem: pro každou hranu v G, vytvořte vrchol v L (G); za každé dva okraje v G které mají společný vrchol, vytvoří hranu mezi odpovídajícími vrcholy v L (G).
Řádkový graf jmen pochází z příspěvku od Harary & Norman (1960) ačkoli oba Whitney (1932) a Krausz (1943) použil konstrukci před tím.[1] Mezi další výrazy používané pro spojnicový graf patří krycí graf, derivát, dual-edge-to-vertex, sdružené, reprezentativní grafa ϑ-obrazom,[1] stejně jako hranový graf, výměnný graf, adjungovaný grafa odvozený graf.[2]
Hassler Whitney (1932 ) prokázal, že u jednoho výjimečného případu byla struktura a připojený graf G lze zcela obnovit z jeho spojnicového grafu.[3] Mnoho dalších vlastností spojnicových grafů následuje překladem vlastností podkladového grafu z vrcholů na hrany a podle Whitneyho věty lze stejný překlad provést také opačným směrem. Čárové grafy jsou bez drápů a spojnicové grafy bipartitní grafy jsou perfektní. Čárové grafy se vyznačují devíti zakázané podgrafy a lze je rozpoznat v lineární čas.
Byla studována různá rozšíření konceptu spojnicového grafu, včetně spojnicových grafů spojnicových grafů, spojnicových grafů multigrafů, spojnicové grafy hypergrafů a spojnicové grafy vážených grafů.
Formální definice
Daný graf G, jeho spojnicový graf L(G) je graf takový, že
- každý vrchol z L(G) představuje hranu G; a
- dva vrcholy L(G) jsou přilehlý právě tehdy, pokud jejich odpovídající okraje sdílejí společný koncový bod ("jsou incidenty") v G.
To znamená, že je průsečíkový graf okrajů G, představující každou hranu sadou jejích dvou koncových bodů.[2]
Příklad
Následující obrázky ukazují graf (vlevo, s modrými vrcholy) a jeho spojnicový graf (vpravo, se zelenými vrcholy). Každý vrchol spojnicového grafu je zobrazen s dvojicí koncových bodů odpovídající hrany v původním grafu. Například zelený vrchol vpravo označený 1,3 odpovídá okraji vlevo mezi modrými vrcholy 1 a 3. Zelený vrchol 1,3 sousedí se třemi dalšími zelenými vrcholy: 1,4 a 1,2 (odpovídající k hranám sdílejícím koncový bod 1 v modrém grafu) a 4,3 (odpovídá hraně sdílející koncový bod 3 v modrém grafu).
Graf G
Vrcholy v L (G) vytvořené z hran v G
Přidané hrany v L (G)
Čárový graf L (G)
Vlastnosti
Přeložené vlastnosti podkladového grafu
Vlastnosti grafu G které závisí pouze na sousedství mezi hranami, lze převést na ekvivalentní vlastnosti v L(G), které závisí na sousedství mezi vrcholy. Například a vhodný v G je množina hran, z nichž dvě nejsou sousední, a odpovídá množině vrcholů v L(G) žádné ze dvou sousedících, tj. an nezávislá sada.[4]
Tím pádem,
- Čárový graf a připojený graf je připojen. Li G je připojen, obsahuje a cesta spojením jakýchkoli dvou jeho okrajů, což se promění v cestu dovnitř L(G) obsahující kterékoli dva z vrcholů L(G). Nicméně graf G který má některé izolované vrcholy, a proto je odpojen, může přesto mít připojený spojnicový graf.[5]
- Čárový graf má artikulační bod právě když má podkladový graf a most u nichž žádný z koncových bodů nemá stupeň jedna.[2]
- Pro graf G s n vrcholy a m hran, počet vrcholů spojnicového grafu L(G) je ma počet okrajů L(G) je polovina součtu čtverců stupňů vrcholů v G, mínus m.[6]
- An nezávislá sada v L (G) odpovídá a vhodný v G. Zejména a maximální nezávislá množina v L (G) odpovídá maximální shoda v G. Vzhledem k tomu, že v polynomiálním čase lze najít maximální shodu, mohou se objevit i maximální nezávislé množiny spojnicových grafů, a to i přes tvrdost úlohy maximální nezávislé množiny pro obecnější rodiny grafů.[4] Podobně, a duhová nezávislá sada v L(G) odpovídá a duhová shoda v G.
- The hranové chromatické číslo grafu G se rovná vrchol chromatického čísla jeho spojnicového grafu L(G).[7]
- Čárový graf hranový tranzitivní graf je vrchol-tranzitivní. Tuto vlastnost lze použít ke generování rodin grafů, které (jako Petersenův graf ) jsou vrcholné tranzitivní, ale nejsou Cayleyovy grafy: pokud G je hranový přechodový graf, který má nejméně pět vrcholů, není bipartitní a má liché stupně vrcholů, pak L(G) je vertex-tranzitivní non-Cayleyův graf.[8]
- Pokud graf G má Eulerův cyklus, tedy pokud G je spojen a má sudý počet hran na každém vrcholu, poté spojnicový graf G je Hamiltonian. Ne všechny Hamiltonovské cykly v liniových grafech však pocházejí z Eulerových cyklů tímto způsobem; například spojnicový graf hamiltonovského grafu G je sám o sobě Hamiltonian, bez ohledu na to, zda G je také Eulerian.[9]
- Pokud jsou dva jednoduché grafy izomorfní potom jsou jejich spojnicové grafy také izomorfní. The Věta o izomorfismu Whitneyho grafu poskytuje konverzaci pro všechny grafy kromě jedné dvojice.
- V souvislosti s teorií složité sítě si čárový graf náhodné sítě zachovává mnoho vlastností sítě, například vlastnictví malého světa (existence krátkých cest mezi všemi dvojicemi vrcholů) a tvar jeho rozdělení stupňů.[10] Evans & Lambiotte (2009) pozorujte, že na spojnicový graf lze použít jakoukoli metodu pro nalezení vrcholů klastrů ve složité síti a místo toho je použít k seskupení jeho hran.
Věta o isomorfismu Whitney

Pokud jsou spojnicové grafy dvou spojené grafy jsou izomorfní, pak podkladové grafy jsou izomorfní, s výjimkou trojúhelníkového grafu K.3 a dráp K.1,3, které mají izomorfní spojnicové grafy, ale samy o sobě nejsou izomorfní.[3]
Stejně jako K.3 a K.1,3, existují některé další výjimečné malé grafy s vlastností, že jejich spojnicový graf má vyšší stupeň symetrie než samotný graf. Například diamantový graf K.1,1,2 (dva trojúhelníky sdílející hranu) má čtyři automatizmy grafů ale jeho spojnicový graf K.1,2,2 má osm. Na ilustraci zobrazeného diamantového grafu není otáčení grafu o 90 stupňů symetrií grafu, ale symetrií jeho spojnicového grafu. Všechny tyto výjimečné případy však mají nejvýše čtyři vrcholy. Posílená verze Whitneyho izomorfismu věta uvádí, že pro spojené grafy s více než čtyřmi vrcholy existuje vzájemná korespondence mezi izomorfismy grafů a izomorfismy jejich spojnicových grafů.[11]
Analogy věty o Whitomorově izomorfismu byly prokázány pro spojnicové grafy multigrafy, ale v tomto případě jsou komplikovanější.[12]
Silně pravidelné a dokonalé spojnicové grafy

Čárový graf celého grafu K.n je také známý jako trojúhelníkový graf, Johnsonův graf J(n, 2) nebo doplněk z Kneserův graf KGn,2. Trojúhelníkové grafy se vyznačují svými spektra, až na n = 8.[13] Mohou být také charakterizovány (opět s výjimkou K.8) jako silně pravidelné grafy s parametry srg (n(n − 1)/2, 2(n − 2), n − 2, 4).[14] Tři silně pravidelné grafy se stejnými parametry a spektrem jako L(K.8) jsou Chang grafy, které lze získat přepínání grafů z L(K.8).
Čárový graf a bipartitní graf je perfektní (vidět Kőnigova věta ), ale nemusí být bipartitní, jak ukazuje příklad drápového grafu. Čárové grafy bipartitních grafů tvoří jeden z klíčových stavebních kamenů dokonalých grafů použitých v důkazu silná dokonalá věta o grafu.[15] Zvláštní případ těchto grafů je věže grafy, spojnicové grafy kompletní bipartitní grafy. Stejně jako spojnicové grafy úplných grafů je lze charakterizovat s jednou výjimkou počtem vrcholů, počtem hran a počtem sdílených sousedů sousedních a nesousedících bodů. Jeden výjimečný případ je L(K.4,4), který sdílí své parametry s Shrikhandův graf. Pokud mají obě strany bipartice stejný počet vrcholů, jsou tyto grafy opět silně pravidelné.[16]
Obecněji graf G se říká, že je řádkový dokonalý graf -li L(G) je perfektní graf. Čárové dokonalé grafy jsou přesně grafy, které neobsahují a jednoduchý cyklus liché délky větší než tři.[17] Ekvivalentně je graf dokonalý po řádcích právě tehdy, když je každý z nich vzájemně propojené komponenty je buď bipartitní, nebo ve formě K.4 (čtyřstěn) nebo K.1,1,n (kniha jednoho nebo více trojúhelníků sdílejících společnou hranu).[18] Každý řádkový dokonalý graf je sám o sobě dokonalý.[19]
Všechny spojnicové grafy jsou grafy bez drápů, grafy bez indukovaný podgraf ve formě třílistého stromu.[20] Stejně jako u obecnějších grafů bez drápů, každý připojený spojnicový graf L(G) se sudým počtem hran má a perfektní shoda;[21] ekvivalentně to znamená, že pokud podkladový graf G má sudý počet hran, jeho hrany lze rozdělit na cesty se dvěma hranami.
Čárové grafy stromy jsou přesně bez drápů blokové grafy.[22] Tyto grafy byly použity k řešení problému v teorie extrémních grafů, konstrukce grafu s daným počtem hran a vrcholů, jejichž největší strom indukované jako podgraf je co nejmenší.[23]
Všechno vlastní čísla z matice sousedství spojnicového grafu jsou alespoň −2. Důvodem je to lze psát jako , kde je matice výskytu bez znaménka předlinkového grafu a je identita. Zejména, je Gramianova matice systému vektorů: všechny grafy s touto vlastností se nazývají zobecněné spojnicové grafy.[24]
Charakterizace a uznání
Clique přepážka

Pro libovolný graf Ga libovolný vrchol proti v G, sada hran dopadajících na proti odpovídá a klika v spojnicovém grafu L(G). Takto vytvořené kliky rozdělují okraje L(G). Každý vrchol L(G) patří přesně dvěma z nich (dvěma klikám odpovídajícím dvěma koncovým bodům odpovídající hrany v G).
Existenci takového oddílu do klik lze použít k charakterizaci spojnicových grafů: Graf L je spojnicový graf nějakého jiného grafu nebo multigrafu tehdy a jen tehdy, když je možné v něm najít kolekci klik L (což umožňuje, aby některé kliky byly jednotlivé vrcholy), které rozdělují okraje L, takže každý vrchol L patří přesně ke dvěma klikám.[20] Je to spojnicový graf grafu (spíše než multigraf), pokud tato sada klik splňuje další podmínku, že žádné dva vrcholy L jsou oba ve stejných dvou klikách. Vzhledem k takové rodině klik, základní graf G pro který L je spojnicový graf lze obnovit vytvořením jednoho vrcholu v G pro každou kliku a hranu dovnitř G pro každý vrchol v L přičemž jeho koncovými body jsou dvě kliky obsahující vrchol v L. Silnou verzí Whitneyho věty o izomorfismu, pokud je podkladovým grafem G má více než čtyři vrcholy, může existovat pouze jeden oddíl tohoto typu.
Tuto charakteristiku lze například použít k zobrazení, že následující graf není spojnicový:
V tomto příkladu nemají hrany směřující vzhůru, doleva a doprava z centrálního vrcholu stupně čtyři, žádné společné kliky. Proto by jakékoli rozdělení okrajů grafu na kliky muselo mít alespoň jednu kliku pro každou z těchto tří hran a všechny tyto tři kliky by se protínaly v tomto středním vrcholu, což by porušovalo požadavek, aby se každý vrchol objevil přesně ve dvou klikách. Zobrazený graf tedy není spojnicový.
Zakázané podgrafy

Další charakterizace spojnicových grafů byla prokázána v Beineke (1970) (a nahlášeno dříve bez důkazu do Beineke (1968) ). Ukázal, že existuje devět minimálních grafů, které nejsou liniovými grafy, takže každý graf, který není liniovým grafem, má jeden z těchto devíti grafů jako indukovaný podgraf. To znamená, že graf je spojnicový graf právě tehdy, když žádná podmnožina jeho vrcholů neindukuje jeden z těchto devíti grafů. Ve výše uvedeném příkladu čtyři nejvyšší vrcholy vyvolávají dráp (tj. A kompletní bipartitní graf K.1,3), zobrazený vlevo nahoře na obrázku zakázaných podgrafů. Z charakterizace Beineke tedy tento příklad nemůže být spojnicový graf. U grafů s minimálním stupněm alespoň 5 je při charakterizaci zapotřebí pouze šest podgrafů v levém a pravém sloupci obrázku.[25]
Algoritmy
Roussopoulos (1973) a Lehot (1974) popsané lineární časové algoritmy pro rozpoznávání liniových grafů a rekonstrukci jejich původních grafů. Sysło (1982) zobecnil tyto metody na řízené grafy. Degiorgi & Simon (1995) popsal efektivní datovou strukturu pro udržování dynamického grafu s výhradou vkládání a mazání vrcholů a udržování reprezentace vstupu jako spojnicového grafu (pokud existuje) v čase úměrném počtu změněných hran v každém kroku.
Algoritmy Roussopoulos (1973) a Lehot (1974) jsou založeny na charakterizaci spojnicových grafů zahrnujících liché trojúhelníky (trojúhelníky v spojnicovém grafu s vlastností, že existuje další vrchol sousedící s lichým počtem vrcholů trojúhelníku). Algoritmus Degiorgi & Simon (1995) používá pouze Whitneyho větu o izomorfismu. Je to komplikováno potřebou rozpoznat odstranění, která způsobí, že se ze zbývajícího grafu stane spojnicový graf, ale když se specializuje na problém statického rozpoznávání, je třeba provést pouze vložení a algoritmus provede následující kroky:
- Vytvořte vstupní graf L přidáním vrcholů jeden po druhém, v každém kroku výběrem vrcholu k přidání, který sousedí s alespoň jedním dříve přidaným vrcholem. Při přidávání vrcholů do L, udržovat graf G pro který L = L(G); pokud algoritmus někdy nedokáže najít vhodný graf G, pak vstup není spojnicový graf a algoritmus končí.
- Při přidávání vrcholu proti do grafu L(G) pro který G má čtyři nebo méně vrcholů, může se stát, že reprezentace řádkového grafu není jedinečná. Ale v tomto případě je rozšířený graf dostatečně malý, aby jeho reprezentaci jako spojnicového grafu bylo možné najít pomocí a hledání hrubou silou v konstantním čase.
- Při přidávání vrcholu proti do většího grafu L který se rovná spojnicovému grafu jiného grafu G, nechť S být podgrafem G tvořené hranami, které odpovídají sousedům proti v L. Koukni na tohle S má vrcholový kryt skládající se z jednoho vrcholu nebo dvou nesousedících vrcholů. Pokud jsou v krytu dva vrcholy, zvětšete je G přidáním hrany (odpovídá proti), který spojuje tyto dva vrcholy. Pokud je v krytu pouze jeden vrchol, přidejte do něj nový vrchol G, přiléhající k tomuto vrcholu.
Každý krok trvá buď konstantní čas, nebo zahrnuje nalezení vrcholového krytu konstantní velikosti v grafu S jehož velikost je úměrná počtu sousedůproti. Celkový čas pro celý algoritmus je tedy úměrný součtu počtů sousedů všech vrcholů, které (o handmaking lemma ) je úměrný počtu vstupních hran.
Iterace operátoru čárového grafu
van Rooij & Wilf (1965) zvažte posloupnost grafů
Ukazují, že kdy G je konečný připojený graf, pro tuto sekvenci jsou možné pouze čtyři chování:
- Li G je graf cyklu pak L(G) a každý následující graf v tomto pořadí jsou izomorfní na G sám. Toto jsou jediné spojené grafy, pro které L(G) je izomorfní s G.[26]
- Li G je dráp K.1,3, pak L(G) a všechny následující grafy v pořadí jsou trojúhelníky.
- Li G je graf cesty pak každý následující graf v sekvenci je kratší cestou, dokud posloupnost nakonec nekončí znakem prázdný graf.
- Ve všech zbývajících případech se velikost grafů v této posloupnosti nakonec bez omezení zvětší.
Li G není připojen, tato klasifikace platí zvlášť pro každou komponentu G.
Pro připojené grafy, které nejsou cestami, produkují všechny dostatečně vysoké počty iterací operace spojnicového grafu grafy, které jsou Hamiltonovské.[27]
Zobecnění
Mediální grafy a konvexní mnohostěny
Když rovinný graf G má maximum stupeň vrcholu tři, jeho spojnicový graf je rovinný a každé rovinné vložení G lze rozšířit na vložení L(G). Existují však rovinné grafy s vyšším stupněm, jejichž spojnicové grafy jsou neplanární. Mezi ně patří například 5hvězdičkový K.1,5, drahokamový graf vytvořeno přidáním dvou nepřekračujících úhlopříček v pravidelném pětiúhelníku a vše konvexní mnohostěn s vrcholem stupně čtyři nebo více.[28]
Alternativní konstrukce, mediální graf, se shoduje s čárovým grafem pro rovinné grafy s maximálním stupněm tři, ale vždy je rovinný. Má stejné vrcholy jako spojnicový graf, ale potenciálně méně hran: dva vrcholy mediálního grafu sousedí právě tehdy, pokud jsou odpovídající dva okraje po sobě jdoucí na nějaké ploše rovinného vkládání. Mediální graf duální graf rovinného grafu je stejný jako mediální graf původního rovinného grafu.[29]
Pro pravidelný mnohostěn nebo jednoduchá mnohostěna, může být operace mediálního grafu reprezentována geometricky operací odříznutí každého vrcholu mnohostěnu rovinou procházející středy všech jeho dopadajících hran.[30] Tato operace je známá jako druhé zkrácení,[31] zdegenerované zkrácení,[32] nebo náprava.[33]
Grafy celkem
Celkový graf T(G) grafu G má jako své vrcholy prvky (vrcholy nebo hrany) G, a má hranu mezi dvěma prvky, kdykoli se jedná o incident nebo sousedí. Celkový graf lze také získat rozdělením každé hrany G a pak se náměstí rozděleného grafu.[34]
Multigrafy
Koncept spojnicového grafu G lze přirozeně rozšířit na případ, kdy G je multigraf. V tomto případě lze charakterizaci těchto grafů zjednodušit: charakterizace ve smyslu klikových oddílů již nemusí bránit tomu, aby dva vrcholy patřily ke stejným klikám, a charakterizace zakázanými grafy má namísto devíti sedm zakázaných grafů.[35]
U multigrafů však existuje větší počet párů neizomorfních grafů, které mají stejné spojnicové grafy. Například kompletní bipartitní graf K.1,n má stejný spojnicový graf jako dipólový graf a Shannonův multigraf se stejným počtem hran. Přesto lze v tomto případě stále odvodit analogie k Whitneyho teorému o izomorfismu.[12]
Řádkové digrafy

Je také možné zobecnit spojnicové grafy na směrované grafy.[36] Li G je směrovaný graf, jeho směrovaný spojnicový graf nebo řádkový digraf má jeden vrchol pro každou hranu G. Dva vrcholy představující směrované hrany z u na proti a od w na X v G jsou spojeny hranou z uv na šx v řádku digraph když proti = w. To znamená, že každý okraj v liniové digrafii G představuje směrovanou cestu délky dva G. The de Bruijn grafy může být vytvořen opakováním tohoto procesu vytváření směrovaných spojnicových grafů, počínaje a kompletní směrovaný graf.[37]
Vážené spojnicové grafy
V spojnicovém grafu L(G), každý vrchol stupně k v původním grafu G vytváří k(k - 1) / 2 hrany v spojnicovém grafu. Pro mnoho typů analýz to znamená uzly vysokého stupně v G jsou v čárovém grafu nadměrně zastoupeny L(G). Zvažte například a náhodná procházka na vrcholech původního grafu G. To projde po nějaké hraně E s určitou frekvencí F. Na druhou stranu tato hrana E je mapován na jedinečný vrchol, řekněme proti, v spojnicovém grafu L(G). Pokud nyní provedeme stejný typ náhodného procházení po vrcholech spojnicového grafu, s jakou frekvencí proti může být zcela odlišný od F. Pokud náš okraj E v G byl připojen k uzlům stupně O (k), bude projet O (k2) častěji v spojnicovém grafu L(G). Jinými slovy, věta o izomorfismu Whitneyho grafu zaručuje, že spojnicový graf téměř vždy kóduje topologii původního grafu G věrně, ale nezaručuje to, že dynamika těchto dvou grafů má jednoduchý vztah. Jedním z řešení je sestrojení váženého spojnicového grafu, tj. Spojnicového grafu s vážené hrany. Existuje několik přirozených způsobů, jak toho dosáhnout.[38] Například pokud hrany d a E v grafu G jsou incidenty na vrcholu proti s titulem k, pak v spojnicovém grafu L(G) hrana spojující dva vrcholy d a E může mít hmotnost 1 / (k - 1). Tímto způsobem každá hrana dovnitř G (za předpokladu, že ani jeden konec není spojen s vrcholem stupně 1) bude mít v spojnicovém grafu sílu 2 L(G) odpovídající dvěma koncům, ve kterých má hrana G. Je jednoduché rozšířit tuto definici váženého spojnicového grafu na případy, kdy byl použit původní graf G bylo namířeno nebo dokonce váženo.[39] Zásadou ve všech případech je zajistit spojnicový graf L(G) odráží dynamiku i topologii původního grafu G.
Čárové grafy hypergrafů
Okraje a hypergraf může tvořit svévolně rodina sad, takže spojnicový graf hypergrafu je stejný jako průsečíkový graf sad z rodiny.
Graf disjunktnosti
The graf disjunktnosti z G, označeno D (G), je konstruován následujícím způsobem: pro každou hranu v G, vytvořte vrchol v D (G); za každé dva okraje v G to ano ne mít společný vrchol, vytvořit hranu mezi jejich odpovídajícími vrcholy v D (G).[40] Jinými slovy, D (G) je doplňkový graf z L (G). A klika v D (G) odpovídá nezávislé množině v L (G) a naopak.
Poznámky
- ^ A b Hemminger & Beineke (1978), str. 273.
- ^ A b C Harary (1972), str. 71.
- ^ A b Whitney (1932); Krausz (1943); Harary (1972), Věta 8,3, s. 72. Harary dává zjednodušený důkaz této věty od Jung (1966).
- ^ A b Paschos, Vangelis Th. (2010), Kombinatorická optimalizace a teoretická informatika: Rozhraní a perspektivy, John Wiley & Sons, str. 394, ISBN 9780470393673,
Je zřejmé, že mezi shody grafu a nezávislými sadami jeho spojnicového grafu existuje vzájemná korespondence.
- ^ Na potřebu zohlednit izolované vrcholy při zvažování konektivity spojnicových grafů poukazuje Cvetković, Rowlinson & Simić (2004), str. 32.
- ^ Harary (1972), Věta 8.1, str. 72.
- ^ Diestel, Reinhard (2006), Teorie grafů, Postgraduální texty z matematiky, 173, Springer, str. 112, ISBN 9783540261834. Také v bezplatné online vydání, Kapitola 5 („Barvení“), s. 118.
- ^ Lauri, Josef; Scapellato, Raffaele (2003), Témata v automatických grafech a rekonstrukcích, London Mathematical Society Student Texts, 54, Cambridge: Cambridge University Press, str. 44, ISBN 0-521-82151-7, PAN 1971819. Lauri a Scapellato připisují tento výsledek Markovi Watkinsovi.
- ^ Harary (1972), Věta 8.8, s. 80.
- ^ Ramezanpour, Karimipour & Mashaghi (2003).
- ^ Jung (1966); Degiorgi & Simon (1995).
- ^ A b Zverovich (1997)
- ^ van Dam, Edwin R .; Haemers, Willem H. (2003), „Které grafy jsou určeny jejich spektrem?“, Lineární algebra a její aplikace, 373: 241–272, doi:10.1016 / S0024-3795 (03) 00483-X, PAN 2022290. Viz zejména Proposition 8, str. 262.
- ^ Harary (1972), Věta 8.6, s. 79. Harary připisuje tento výsledek nezávislým dokumentům L. C. Changa (1959) a A. J. Hoffman (1960).
- ^ Chudnovský, Maria; Robertson, Neil; Seymour, Paule; Thomas, Robin (2006), „Silná dokonalá věta o grafu“, Annals of Mathematics, 164 (1): 51–229, arXiv:matematika / 0212070, doi:10.4007 / annals.2006.164.51, S2CID 119151552. Viz také Roussel, F .; Rusu, I .; Thuillier, H. (2009), „Silná dokonalá domněnka grafu: 40 let pokusů a její řešení“, Diskrétní matematika, 309 (20): 6092–6113, doi:10.1016 / j.disc.2009.05.024, PAN 2552645.
- ^ Harary (1972), Věta 8.7, s. 79. Harary připisuje tuto charakteristiku spojnicových grafů úplných bipartitních grafů Moonovi a Hoffmanovi. Případ stejného počtu vrcholů na obou stranách dříve prokázal Shrikhande.
- ^ Trotter (1977); de Werra (1978).
- ^ Maffray (1992).
- ^ Trotter (1977).
- ^ A b Harary (1972), Věta 8.4, s. 74, poskytuje tři ekvivalentní charakterizace spojnicových grafů: rozdělení okrajů na kliky, vlastnost bytí bez drápů a zvláštní diamant - zdarma a devět zakázaných grafů Beineke.
- ^ Sumner, David P. (1974), "Grafy s 1 faktory", Proceedings of the American Mathematical SocietyAmerická matematická společnost, 42 (1): 8–12, doi:10.2307/2039666, JSTOR 2039666, PAN 0323648. Las Vergnas, M. (1975), „Poznámka k párování v grafech“, Cahiers du Centre d'Études de Recherche Opérationnelle, 17 (2–3–4): 257–260, PAN 0412042.
- ^ Harary (1972), Věta 8,5, s. 78. Harary připisuje výsledek Gary Chartrand.
- ^ Erdős, Paul; Saks, Michael; Sós, Vera T. (1986), „Maximum induced trees in graphs“, Journal of Combinatorial Theory, Series B, 41 (1): 61–79, doi:10.1016/0095-8956(86)90028-6.
- ^ Cvetković, Rowlinson & Simić (2004).
- ^ Metelsky & Tyshkevich (1997)
- ^ Tento výsledek je také věta 8.2 z Harary (1972).
- ^ Harary (1972), Věta 8.11, s. 81. Harary připisuje tento výsledek Gary Chartrand.
- ^ Sedláček (1964); Greenwell & Hemminger (1972).
- ^ Arciděkan, Dan (1992), „Mediální graf a dualita napětí a proudu“, Diskrétní matematika, 104 (2): 111–141, doi:10.1016 / 0012-365X (92) 90328-D, PAN 1172842.
- ^ McKee, T. A. (1989), „Graficko-teoretický model geografické duality“, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), Ann. New York Acad. Sci., 555, New York: New York Acad. Sci., Str. 310–315, Bibcode:1989NYASA.555..310M, doi:10.1111 / j.1749-6632.1989.tb22465.x, PAN 1018637.
- ^ Pugh, Anthony (1976), Mnohostěn: Vizuální přístup, University of California Press, ISBN 9780520030565.
- ^ Loeb, Arthur Lee (1991), Vesmírné struktury - jejich harmonie a kontrapunkt (5. vydání), Birkhäuser, ISBN 9783764335885.
- ^ Weisstein, Eric W. „Oprava“. MathWorld.
- ^ Harary (1972), str. 82.
- ^ Ryjáček & Vrána (2011).
- ^ Harary & Norman (1960).
- ^ Zhang & Lin (1987).
- ^ Evans & Lambiotte (2009).
- ^ Evans & Lambiotte (2010).
- ^ Meshulam, Roy (01.01.2001). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10,1007 / s004930170006. ISSN 1439-6912. S2CID 207006642.
Reference
- Beineke, L. W. (1968), „Derived graphs of digraphs“, in Sachs, H .; Voss, H.-J .; Walter, H.-J. (eds.), Beiträge zur Graphentheorie, Lipsko: Teubner, s. 17–33.
- Beineke, L. W. (1970), „Charakterizace odvozených grafů“, Journal of Combinatorial Theory, 9 (2): 129–135, doi:10.1016 / S0021-9800 (70) 80019-9, PAN 0262097.
- Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan (2004), Spektrální zobecnění spojnicových grafů, Série přednášek London Mathematical Society, 314, Cambridge: Cambridge University Press, doi:10.1017 / CBO9780511751752, ISBN 0-521-83663-8, PAN 2120511.
- Degiorgi, Daniele Giorgio; Simon, Klaus (1995), „Dynamický algoritmus pro rozpoznávání spojnicového grafu“, Graficko-teoretické koncepty v počítačové vědě (Aachen, 1995), Přednášky v informatice, 1017, Berlín: Springer, s. 37–48, doi:10.1007/3-540-60618-1_64, PAN 1400011.
- Evans, T.S .; Lambiotte, R. (2009), „Čárové grafy, spojovací oddíly a překrývající se komunity“, Fyzický přehled E, 80 (1): 016105, arXiv:0903.2181, Bibcode:2009PhRvE..80a6105E, doi:10.1103 / PhysRevE.80.016105, PMID 19658772.
- Evans, T.S .; Lambiotte, R. (2010), „Čárové grafy vážených sítí pro překrývající se komunity“, Evropský fyzický deník B, 77 (2): 265–272, arXiv:0912.4389, Bibcode:2010EPJB ... 77..265E, doi:10.1140 / epjb / e2010-00261-8, S2CID 119504507.
- Greenwell, D. L .; Hemminger, Robert L. (1972), „Zakázané podgrafy pro grafy s rovinnými spojnicovými grafy“, Diskrétní matematika, 2: 31–34, doi:10.1016 / 0012-365X (72) 90058-1, PAN 0297604.
- Harary, F.; Norman, R. Z. (1960), "Some properties of line digraphs", Rendiconti del Circolo Matematico di Palermo, 9 (2): 161–169, doi:10.1007 / BF02854581, hdl:10338.dmlcz / 128114, S2CID 122473974.
- Harary, F. (1972), "8. Čárové grafy", Teorie grafů (PDF), Massachusetts: Addison-Wesley, str. 71–83.
- Hemminger, R.L .; Beineke, L. W. (1978), „Čárové grafy a spojnicové grafy“, Beineke, L. W .; Wilson, R. J. (eds.), Vybraná témata v teorii grafů, Academic Press Inc., str. 271–305.
- Jung, H. A. (1966), „Zu einem Isomorphiesatz von H. Whitney für Graphen“, Mathematische Annalen (v němčině), 164: 270–271, doi:10.1007 / BF01360250, PAN 0197353, S2CID 119898359.
- Krausz, J. (1943), „Démonstration nouvelle d'un théorème de Whitney sur les réseaux“, Rohož. Fiz. Lapok, 50: 75–85, PAN 0018403.
- Lehot, Philippe G. H. (1974), „Optimální algoritmus pro detekci spojnicového grafu a výstup jeho kořenového grafu“, Deník ACM, 21 (4): 569–575, doi:10.1145/321850.321853, PAN 0347690, S2CID 15036484.
- Maffray, Frédéric (1992), „Jádra v dokonalých liniových grafech“, Journal of Combinatorial Theory, Řada B, 55 (1): 1–8, doi:10.1016 / 0095-8956 (92) 90028-V, PAN 1159851.
- Metelsky, Yury; Tyshkevich, Regina (1997), „On line graphs of linear 3-uniform hypergraphs“, Journal of Graph Theory, 25 (4): 243–251, doi:10.1002 / (SICI) 1097-0118 (199708) 25: 4 <243 :: AID-JGT1> 3.0.CO; 2-K.
- Ramezanpour, A .; Karimipour, V .; Mashaghi, A. (2003), „Generování korelovaných sítí z nekorelovaných“, Phys. Rev., 67 (4): 046107, arXiv:cond-mat / 0212469, Bibcode:2003PhRvE..67d6107R, doi:10.1103 / physreve.67.046107, PMID 12786436, S2CID 33054818.
- van Rooij, A. C. M .; Wilf, H. S. (1965), „Interchange graph of a finite graph“, Acta Mathematica Hungarica, 16 (3–4): 263–269, doi:10.1007 / BF01904834, hdl:10338.dmlcz / 140421, S2CID 122866512.
- Roussopoulos, N. D. (1973), „A max {m,n} algoritmus pro stanovení grafu H z jeho spojnicového grafu G", Dopisy o zpracování informací, 2 (4): 108–112, doi:10.1016 / 0020-0190 (73) 90029-X, PAN 0424435.
- Ryjáček, Zdeněk; Vrána, Petr (2011), „Čárové grafy multigrafů a Hamiltonova propojenost grafů bez drápů“, Journal of Graph Theory, 66 (2): 152–173, doi:10.1002 / jgt.20498, PAN 2778727.
- Sedláček, J. (1964), "Některé vlastnosti výměnných grafů", Teorie grafů a její aplikace (Proc. Sympos. Smolenice, 1963)Publ. Dům československý akadem. Sci., Praha, s. 145–150, PAN 0173255.
- Sysło, Maciej M. (1982), „Algoritmus označování k rozpoznání liniového grafu a výstupu jeho kořenového grafu“, Dopisy o zpracování informací, 15 (1): 28–30, doi:10.1016/0020-0190(82)90080-1, PAN 0678028.
- Trotter, L. E., Jr. (1977), „Line perfect graphs“, Matematické programování, 12 (2): 255–259, doi:10.1007 / BF01593791, PAN 0457293, S2CID 38906333.
- de Werra, D. (1978), „On line perfect graphs“, Matematické programování, 15 (2): 236–238, doi:10.1007 / BF01609025, PAN 0509968, S2CID 37062237.
- Whitney, H. (1932), „Congruent graphs and the connectivity of graphs“, American Journal of Mathematics, 54 (1): 150–168, doi:10.2307/2371086, hdl:10338.dmlcz / 101067, JSTOR 2371086.
- Zhang, Fu Ji; Lin, Guo Ning (1987), „On the de Bruijn – Good graphs“, Acta Math. Sinica, 30 (2): 195–205, PAN 0891925.
- Зверович, И. Э. (1997), Аналог теоремы Уитни для реберных графов мультиграфов a реберные мультиграфы, Diskretnaya Matematika (v Rusku), 9 (2): 98–105, doi:10,4213 / dm478, PAN 1468075. Přeloženo do angličtiny jako Zverovich, I. È. (1997), „Analog Whitneyho věty pro hranové grafy multigrafů a hranové multigrafy“, Diskrétní matematika a aplikace, 7 (3): 287–294, doi:10.1515 / dma.1997.7.3.287, S2CID 120525090.