Strona 1 z 1
Ilość krawędzi w grafie
: 29 gru 2014, o 19:12
autor: mCichy13
Witam czy jeśli mamy jakiś graf o n wierzchołkach i wiemy że stopień każdego wierzchołka równy jest 30 to czy wzór na ilość krawędzi będzie wyglądał tak czy coś przeoczyłem
\(\displaystyle{ \frac{n \cdot 30}{2}}\)
Ilość krawędzi w grafie
: 29 gru 2014, o 21:34
autor: kicaj
będzie \(\displaystyle{ 2\cdot 30n}\)
Ilość krawędzi w grafie
: 29 gru 2014, o 22:00
autor: mCichy13
kicaj pisze:będzie \(\displaystyle{ 2\cdot 30n}\)
Możesz to jakoś wytłumaczyć? Co jeśli n=31 więc mamy graf pełny a liczba jego krawędzi to
\(\displaystyle{ {31 \choose 2} = \frac{31 \cdot 30}{2}}\)
Ilość krawędzi w grafie
: 1 sty 2015, o 11:49
autor: PiotrowskiW
mCichy13
Twój wzór wygląda dobrze.
Udowodnij go indukcyjnie najlepiej.
Ilość krawędzi w grafie
: 5 sty 2015, o 11:43
autor: bakala12
A tam indukcyjnie. Dowód jest dużo prostszy. Zliczamy po prostu krawędzie. Z każdego z \(\displaystyle{ n}\) wierzchołków wychodzi \(\displaystyle{ 30}\) krawędzi. Każdą krawędź łączy dwa wierzchołki, więc jest liczona dwukrotnie. Stąd liczba krawędzi to \(\displaystyle{ \frac{n\cdot 30 }{2}}\)