Indukovaná cesta - Induced path

Indukovaná dráha délky čtyři v a krychle. Nalezení nejdelší indukované dráhy v hyperkrychli je známé jako had-in-the-box problém.

V matematický oblast teorie grafů, an indukovaná cesta v neorientovaném grafu G je cesta to je indukovaný podgraf z G. To znamená, že se jedná o posloupnost vrcholů v G tak, že každé dva sousední vrcholy v sekvenci jsou spojeny hranou v Ga každé dva nesousedící vrcholy v sekvenci nejsou spojeny žádnou hranou v G. Indukovaná cesta se někdy nazývá a hada problém hledání dlouhých indukovaných cest v hyperkrychlové grafy je známý jako had-in-the-box problém.

Podobně an indukovaný cyklus je cyklus to je indukovaný podgraf G; indukované cykly se také nazývají akordové cykly nebo (pokud je délka cyklu čtyři nebo více) díry. An antihole je díra v doplněk z G, tj. antihole je doplněk díry.

Délka nejdelší indukované dráhy v grafu byla někdy nazývána číslo objížďky grafu;^[1] pro řídké grafy, mít ohraničené číslo objížďky je ekvivalentní mít ohraničené hloubka stromu.^[2] The indukované číslo cesty grafu G je nejmenší počet indukovaných cest, do kterých lze rozdělit vrcholy grafu,^[3] a úzce související číslo krytu cesty z G je nejmenší počet indukovaných cest, které společně zahrnují všechny vrcholy G.^[4] The obvod grafu je délka jeho nejkratšího cyklu, ale tento cyklus musí být indukovaným cyklem, protože k vytvoření kratšího cyklu lze použít jakýkoli akord; z podobných důvodů zvláštní obvod grafu je také délka jeho nejkratšího lichého indukovaného cyklu.

Příklad

Na obrázku je krychle, graf s osmi vrcholy a dvanácti hranami a indukovaná cesta délky čtyři v tomto grafu. Jednoduchá analýza případů ukazuje, že v krychli již nemůže být indukovaná cesta, i když má indukovaný cyklus délky šest. Problém najít nejdelší indukovanou cestu nebo cyklus v hyperkrychli, kterou nejprve představuje Kautz (1958), je známý jako had-in-the-box problém, a to bylo studováno značně kvůli jeho aplikacím v teorii kódování a inženýrství.

Charakterizace rodin grafů

Mnoho důležitých rodin grafů lze charakterizovat z hlediska indukovaných cest nebo cyklů grafů v rodině.

• Triviálně jsou spojené grafy bez indukované dráhy délky dva kompletní grafy a připojené grafy bez indukovaného cyklu jsou stromy.
• A graf bez trojúhelníků je graf bez indukovaného cyklu délky tři.
• The cographs jsou přesně grafy bez indukované dráhy délky tři.
• The chordální grafy jsou grafy bez indukovaného cyklu délky čtyři nebo více.
• The rovnoměrné díry bez grafů jsou grafy, které neobsahují žádné indukované cykly se sudým počtem vrcholů.
• The triviálně dokonalé grafy jsou grafy, které nemají ani indukovanou dráhu délky tři, ani indukovaný cyklus délky čtyři.
• Silnou dokonalou větou grafu, perfektní grafy jsou grafy bez zvláštní díry a bez zvláštní díry.
• The vzdálenostně dědičné grafy jsou grafy, ve kterých je každá indukovaná cesta nejkratší cestou, a grafy, ve kterých mají každé dvě indukované cesty mezi stejnými dvěma vrcholy stejnou délku.
• The blokové grafy jsou grafy, ve kterých je nanejvýš jedna indukovaná cesta mezi libovolnými dvěma vrcholy, a spojené blokové grafy jsou grafy, ve kterých existuje přesně jedna indukovaná cesta mezi dvěma dvěma vrcholy.

Algoritmy a složitost

Je to NP-úplné určit, pro graf G a parametr k, zda má graf alespoň indukovanou dráhu délky k. Garey & Johnson (1979) připíše tento výsledek nepublikované komunikaci ze dne Mihalis Yannakakis. Tento problém však lze vyřešit v polynomiálním čase pro určité rodiny grafů, jako jsou například asteroidní trojnásobné grafy^[5] nebo grafy bez dlouhých děr.^[6]

Je také NP-úplné určit, zda lze vrcholy grafu rozdělit na dvě indukované cesty nebo dva indukované cykly.^[7] V důsledku toho je určení čísla indukované dráhy grafu NP-těžké.

Složitost aproximace nejdelší indukované dráhy nebo problémů cyklu může souviset s hledáním velkých nezávislé sady v grafech následující redukcí.^[8] Z libovolného grafu G s n vrcholy, tvoří další graf H s dvakrát větším počtem vrcholů než Gpřidáním do G n(n - 1) / 2 vrcholy, z nichž každý má dva sousedy, jeden pro každou dvojici vrcholů G. Pak pokud G má nezávislou sadu velikostí k, H musí mít indukovanou cestu a indukovaný cyklus délky 2k, vytvořené střídáním vrcholů nezávislé množiny G s vrcholy Já. Naopak, pokud H má indukovanou cestu nebo cyklus délky k, libovolná maximální sada nesousedících vrcholů v G z této cesty nebo cyklu tvoří samostatný soubor G alespoň velikosti k/ 3. Tedy velikost maximálního nezávislého souboru G je v konstantním faktoru velikosti nejdelší indukované dráhy a nejdelší indukovaného cyklu v H. Proto podle výsledků Håstad (1996) na nepřístupnosti nezávislých množin, pokud NP = ZPP, neexistuje polynomiální časový algoritmus pro aproximaci nejdelší indukované dráhy nebo nejdelšího indukovaného cyklu na faktor O (n^1/2-ε) optimálního řešení.

Otvory (a díry v grafech bez chordless cyklů délky 5) v grafu s n vrcholy a hranami m mohou být detekovány v čase (n + m²).^[9]

Atomové cykly

Atomové cykly jsou zobecněním cyklů bez akordů, které neobsahují žádné n-chordy. Vzhledem k určitému cyklu, an n-chord je definován jako cesta délky n spojení dvou bodů na cyklu, kde n je menší než délka nejkratší cesty v cyklu spojující tyto body. Pokud cyklus nemá n-chordy, nazývá se to atomový cyklus, protože jej nelze rozložit na menší cykly.^[10]V nejhorším případě lze atomové cykly v grafu vyjmenovat v O (m²) čas, kde m je počet hran v grafu.

Poznámky

Reference