Geodetický graf - Geodetic graph

V teorii grafů je geodetický graf neorientovaný graf , takže mezi každým dvěma vrcholy existuje jedinečná (nevážená) nejkratší cesta.

Geodetické grafy představil v roce 1962 Øystein Ore , který poznamenal, že zobecňují vlastnost stromů (ve kterých existuje jedinečná cesta mezi každým dvěma vrcholy bez ohledu na vzdálenost), a požádal o jejich charakterizaci. Ačkoli tyto grafy lze rozpoznat v polynomiálním čase , „o více než šedesát let později je úplná charakterizace stále nepolapitelná“.

Příklady

Každý strom , každý úplný graf a každý graf cyklu liché délky je geodetický.

Pokud jde o geodetický graf, pak nahrazením každé hrany cestou stejné liché délky vznikne další geodetický graf. V případě úplného grafu je možný obecnější vzor nahrazení cestami: pro každý vrchol zvolte nezáporné celé číslo a každou hranu rozdělte přidáním vrcholů. Potom je výsledný rozdělený úplný graf geodetický a každý geodetický rozdělený kompletní graf lze získat tímto způsobem. ${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle f (v)}$${\ displaystyle v}$${\ displaystyle uv}$${\ displaystyle f (u) + f (v)}$

Související třídy grafů

Blok graf , zvláštní případ geodetické grafu

Petersen graf , jeden z geodetických grafů průměru dva

Pokud je každá vzájemně propojená součást grafu geodetická, pak je samotný graf geodetický. Zejména každý blokový graf (grafy, ve kterých jsou vzájemně propojené komponenty úplné ) je geodetický. Podobně, protože cyklický graf je geodetický, když má lichou délku, každý kaktusový graf, ve kterém mají cykly lichou délku, je také geodetický. Tyto kaktusové grafy jsou přesně spojené grafy, ve kterých mají všechny cykly lichou délku. Silnější je , že rovinný graf je geodetický právě tehdy, když všechny jeho vzájemně propojené komponenty jsou buď liché délky cyklů, nebo geodetické členění čtyřvertexové kliky.

Výpočetní složitost

Geodetické grafy mohou být rozpoznány v polynomiálním čase pomocí variace šíře prvního vyhledávání, které dokáže detekovat několik nejkratších cest, počínaje každým vrcholem grafu. Geodetické grafy nemohou obsahovat indukovaný graf se čtyřmi vrcholovými cykly ani indukovaný diamantový graf , protože tyto dva grafy nejsou geodetické. Zejména jako podmnožina grafů bez diamantů mají geodetické grafy tu vlastnost, že každá hrana patří do jedinečné maximální kliky ; v této souvislosti byly maximální kliky také nazývány řádky . Z toho vyplývá, že problém nalezení maximálních klik nebo maximálně vážených klik lze vyřešit v polynomiálním čase pro geodetické grafy uvedením všech maximálních klik. Širší třída grafů, které nemají indukovaný čtyřtakt nebo diamant, se nazývají „slabě geodetické“; to jsou grafy, kde vrcholy ve vzdálenosti přesně dva od sebe mají jedinečnou nejkratší cestu.

Průměr dva

U grafů o průměru dva (tj. U grafů, ve kterých jsou všechny vrcholy od sebe vzdáleny nejvýše dva) se geodetické a slabě geodetické grafy shodují. Každý geodetický graf o průměru dva je jednoho ze tří typů:

• blokový graf, ve kterém jsou všechny maximální kliky spojeny v jednom sdíleném vrcholu, včetně grafů větrného mlýna ,
• silně pravidelný graf s parametrem (počet společných sousedů pro každou nesousedící dvojici vrcholů) rovnající se jedné, nebo${\ displaystyle \ mu}$
• graf s přesně dvěma různými stupni vrcholů .

Mezi silně pravidelné geodetické grafy patří graf s pěti vertexovými cykly, Petersenův graf a Hoffman-Singletonův graf . Navzdory dalšímu výzkumu vlastností, které takový graf musí mít, není známo, zda existuje více těchto grafů, nebo nekonečně mnoho z těchto grafů.

Geodetické grafy o průměru dva a dvou různých stupních nemohou mít trojúhelník složený z vrcholů obou stupňů. Mohou být zkonstruovány z jakékoli konečné afinní roviny přidáním do grafu dopadu bodové čáry roviny další hrany mezi vrcholy odpovídajícími každé dvě paralelní linii. Pro binární afinní rovinu se čtyřmi body a šesti dvoubodovými liniemi ve třech paralelních párech je výsledkem této konstrukce Petersenův graf, ale pro konečné afinní roviny vyššího řádu vytváří grafy se dvěma různými stupni. Jsou známy i další související konstrukce geodetických grafů z konečných geometrií, ale není známo, zda tyto vyčerpávají všechny možné geodetické grafy o průměru dva a dvou různých stupních.

Reference