Zakázané podgrafy
Úloha číslo: 3576
Najděte všechny grafy, které jako podgraf neobsahují:
Varianta
Cestu délky \(2\).
Nápověda
Omezte se na souvislé grafy.
Řešení
Obsahuje-li nějaká komponenta zakázaný podgraf, zůstane tento podgraf i ve výsledném grafu.
Protože zakázaný podgraf je souvislý, pokud by ho nějaký graf obsahoval, šlo by tento graf nalézt v nějaké komponentě.
Z tohoto argumentu plyne, že nemá-li \(G\) obsahovat nějaký zakázaný souvislý graf, je \(G\) disjunktním sjednocením souvislých grafů (komponent), z nichž žádná neobsahuje zakázaný graf.
Souvislé grafy bez cest délky \(2\) (tyto značíme podle počtu vrcholů \(P_3\)) jsou jen \(K_1\) a \(K_2\). Libovolný souvislý graf na alespoň třech vrcholech obsahuje nějaký souvislý graf na třech vrcholech a ty jsou jen dva: \(P_3\) a \(C_3\). První z nich je zakázaný a z druhého vznikne zakázaný odebráním libovolné hrany.
Odpověď
Grafy bez cest délky \(2\) jsou disjunktní sjednocení \(K_1\) a \(K_2\).
Varianta
Cestu délky \(3\).
Řešení
Komponenty \(G\) mohou být \(K_1\), \(K_2\), \(K_3\) a \(K_{1,k}\).
První tři neobsahují čtyřvrcholovou cestu délky 3 (značíme \(P_4\)) už kvůli počtu vrcholů.
Hvězdy \(K_{1,k}\) mají za podgrafy menší hvězdy a grafy bez hran, tedy nikoli \(P_4\).
Pokud \(G\) má komponentu jinou než uvedenou, musí mít tato komponenta alespoň čtyři vrcholy (všechny menší grafy jsou v našem seznamu).
Jsou-li v této komponentě dva vrcholy \(u\) a \(v\) ve vzdálenosti větší než dvě, potom první čtyři vrcholy nejkratší cesty z \(u\) do \(v\) dávají zakazáný \(P_4\). V opačném případě tato komponenta vznikla přidáním alespoň jedné hrany do \(K_{1,k}\) s \(k\ge 3\). Zakázané \(P_4\) najdeme tak, že nejprve vezmeme tuto přidanou hranu, pak hranu do prostředního vrcholu a nakonec cestu prodloužíme do nějakého doposud nepoužitého vrcholu (protože \(k\ge 3\), takový nepoužitý vrchol jistě existuje).
Odpověď
Grafy bez cest délky \(3\), jsou disjunktní sjednocení \(K_1\), \(K_2\), \(K_3\) a \(K_{1,k}\).
Varianta
Žádnou sudou kružnici.
Odpověď
Grafy bez sudých kružnic vzniknou z lesa (t.j. grafu bez kružnic) přidáním dodatečných hran tak, že s každou hranou přibude nejvýše jedna kružnice a to liché délky.
Jinými slovy, mezi konci přidávané hrany musí existovat nejvýše jedna cesta (t.j. nesmí ležet na kružnici) a tato cesta, existuje-li, má sudou délku.
Nelze mít dvě liché kružnice, které sdílejí nějaké hrany – symetrická diference jejich množin hran by dala sudý cyklus.