Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

#1 28. 01. 2018 16:13

clifer4
Zelenáč
Příspěvky: 1
Reputace:   0 
 

Teória grafov | Prienik podgrafov

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í):

//forum.matweb.cz/upload3/img/2018-01/52057_graf.PNG

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

  • (téma jako vyřešené označil(a) Honzc)

#2 31. 01. 2018 17:00

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

Re: Teória grafov | Prienik podgrafov

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

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech