Matematické Fórum

↑ Wotton:

ok a jak jsi k tomu prosím přišel?:)
víš si rady s tou dvojkou?

↑ Kondr:

je to tedy ten první obrázek?

↑ SweetNelli:

Poněvač je úkolem najít nějaký graf daných vlastností, tak prostě tak, že jsem to zkoušel. Jinak to asi nejde.

Co se tyka dvojky, tak tu sem neřešil z časových důvodů. Dšlal bych to asi takhle:

Nejprve bys měla dokázat že kařdé dva grafy se 4 vrcholy a stejným skóre jsou izomorfní (pokud se nepletu, tak to platí). Teď si vypíšem všechny možný skóre grafu o 4 vrcholech. Poněvač se jedná o kombince s opakováním (a protože součet musí být sudý), tak horní odhad je což je 35, Naštěstí nejsou všechny řešení. Zajímají nás tedy jen tyto skóre:
0,0,0,0
0,0,1,1
0,1,1,2
0,2,2,2
1,1,1,1
1,1,1,3
1,1,2,2
1,2,2,3
2,2,2,2
2,2,3,3
3,3,3,3

Pro ostatní celkem jedoduše dokážeš, že nemůžou být skóre nějakého grafu. Ukážu důkaz například pro 1,1,3,3. Označme si A množinu vrcholů stupně 3. Nyní musí z množiny A do mnořiny V(G)-A vést (minimálně) 4 hrany. Součet stupňů všech vrcholů v mnořině V(G)-A je ale jen 2, což je spor.

Nyní už musíš jen pro každou mořnost nakreslit graf. K tomu můžeš použít například Kondrův odkaz. Důkaz že jsou všechny už jsme provedli.

↑ Kondr:

ano je to jasné, pomohl by jsi mi prosím s tím důkazem? - že každé dva grafy se 4 vrcholy  a stejným skorem jsou izomorfní?

jj na tu stránku jsem koukala, ale přímo obrázky tam nejsou nakreslený, jen počet kolik jich je , ale obrázky se k této úloze nevztahují