Teoria grafów

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
zawistus
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 14 cze 2020, 10:26

Teoria grafów

Post autor: zawistus » 14 cze 2020, 10:27

Hej, prośba o pomoc z zadaniem i wytłumaczenie. Dzięki z góry
Dla których z wymienionych liczb krawędzi: 30, 36, 42,48, istnieje graf spójny o 10 wierzchołkach?

kerajs
Fachowiec
Fachowiec
Posty: 1919
Rejestracja: 14 lis 2016, 15:38
Podziękowania: 10 razy
Otrzymane podziękowania: 820 razy
Płeć:

Re: Teoria grafów

Post autor: kerajs » 14 cze 2020, 13:46

Graf pełny o 10 wierzchołkach ma \(\frac{9 \cdot 10}{2}=45\) krawędzi . Wystarczy wykreślić nadmiarowe krawędzie aby dostać grafy o 30, 36, 42 krawędziach. Albo dopisz trzy pętelki a dostaniesz taki z 48 krawędziami.