Matematické Fórum

Zdravím, rád by som sa spýtal na správny postup k úlohe tohto typu:

Uvažujme jednoduchý neorientovaný graf G na vrcholech {a,b,c,d,e,f,g,h} zadaný následujícím výčtem hran:
   E(G) = {ab,ah,af,bc,be,hc,hg,fe,fg,dc,de,dg}

Váš úkol se týká toho, kolik čtyřúhelníků graf G obsahuje (tj. kolik je v něm různých podgrafů isomorfních kružnici délky čtyři).

= Počet čtyřúhelníků v grafu G  = _ [správně - 6]

= Kolik nejvíce z těchto čtyřúhelníků má (dohromady) neprázdný průnik  = _  [správně - 3]

Jako pomůcku k řešení přidáváme ještě "živý obrázek" grafu G, který vám může pomoci s řešením (avšak nenahrazuje výše uvedené formální zadání):



Túto úlohu som sa pokúšal riešiť tak že som našiel všetky podgrafy (t.j. tých 6 štvoruholníkov), označil som si ich od 1 po 6, ku každému som napísal vrcholy ktoré ho definujú (napr. 1. = {a,b,c,d}, 2. = ...) a každý som porovnal s každým (t.j. 15 možností), resp. aký majú prienik. Z tohto som však vôbec nebol schopný vydedukovať tú správnu odpoveď.

Aký by mal byť správny postup riešenia úloh tohto typu?
Vďaka.