Stopnie wierzchołków grafów

[sympatyczna]

Witam

przykład:
Dla grafu prostego \(\displaystyle{ D=(V,A)}\) gdzie \(\displaystyle{ V=\{2,3,4,5\}}\), \(\displaystyle{ A=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}}\) wyznaczyć stopień dla wszystkich wierzchołków.

Rozwiązanie

\(\displaystyle{ A=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}}\) oraz \(\displaystyle{ V=\{2,3,4,5\}}\) stąd
\(\displaystyle{ D(1)=|A(1)|=|V(1)|=4}\)
\(\displaystyle{ A=\{\{4,1\}, \{4,2\},\{4,3\}\}}\) oraz \(\displaystyle{ V=\{1,2,3\}}\) stąd \(\displaystyle{ D=|A(4)|=|V(4)|= 3}\);
\(\displaystyle{ V(6)= \emptyset \Rightarrow D(6) = 0}\) (wierzchołek izolowany).


Proszę o wytłumaczenia przykładu.

[Yaco_89]

może spróbuj sobie po prostu narysować ten graf żeby zrozumieć o co chodzi? masz zbiór wierzchołków V, a pary z A to wierzchołki między którymi są krawędzie, więc można ten graf narysować dokładnie, definicję stopnia znasz?

[sympatyczna]

znam definicje:
Stopień wierzchołka w grafie to liczba krawędzi sąsiadujących z wierzchołkiem.
Jest on równy sumie liczb wszystkich łuków wchodzących, wychodzących, krawędzi i pętli.

rysunek tez mam:


-- 2 lip 2010, o 15:58 --

Witam

Zadanie: Dla grafu prostego \(\displaystyle{ D=(V,A)}\) gdzie \(\displaystyle{ V=\{1,2,3,4,5,6,7\},
A= \{\{1,6\},\{1,4\},\{2,3\},\{3,4\},\{5,7\},\{6,7\}\}}\) wyznaczyć stopnie dla wszystkich wierzchołków. Sprawdź, że prawdziwe jest podstawowe twierdzenie dotyczące sumy stopni wierzchołków.

rozwiązanie:
V(1)=2
V(2)=1
V(3)=2
V(4)=2
V(5)=1
V(6)=2
V(7)=2

może mi ktoś powiedzieć czy mój tok myślenia jest prawidłowy? i podpowiedzieć co dalej?

-- 2 lip 2010, o 20:39 --

Suma stopni wszystkich wierzchołków jest równa podwojonej liczbie krawędzi grafu.
czyli równa 12?