Liczba wierzcholkow grafu.

czerkawska · Post autor: **czerkawska** » 17 lut 2013, o 21:16

Graf G ma 44 krawedzie. Jaka minimalna liczbe wierzchołków moze miec ten graf jesli
jego wszystkie wierzchołki sa jednakowego stopnia. Czy taki graf regularny o minimalnej liczbie
wierzchołków jest spójny? Jaki jest wzór na obliczenie wierzchołków takiego grafu i jak opisać drugą część zadania?

Zordon · Post autor: **Zordon** » 17 lut 2013, o 21:29

Niech \(\displaystyle{ d}\) to stopień wierzchołków tego grafu.
\(\displaystyle{ dn=44\cdot 2}\)
Zatem \(\displaystyle{ n|88}\). Musi też zachodzić \(\displaystyle{ d+1\leq n}\). Wystarczy teraz zobaczyć do czego prowadzą te warunki.

czerkawska · Post autor: **czerkawska** » 17 lut 2013, o 21:42

szczerze powiem, że nadal nie bardzo wiem co dalej z tym zrobić, możesz troszkę rozjaśnić?

yorgin · Post autor: **yorgin** » 17 lut 2013, o 22:47

Wynika z tego, że \(\displaystyle{ d+1\leq 9}\) oraz \(\displaystyle{ n\geq 11}\)