Archiv diskusního fóra o matematice, 2006–2026
Stránky: 1

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.
Offline
Jedná se o graf krychle, proto se odpovědi dají celkem snadno uhodnout.
Dále doporučuji všimnout si, v kolika čtyřúhelnících se vyskytuje (každá) jedna hrana.
Offline
Stránky: 1