Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 28. 01. 2018 16:13

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

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

http://forum.matematika.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
Moderátor
Místo: Ostrava/Paskov
Příspěvky: 993
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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson