Graf

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
xkatekx
Użytkownik
Użytkownik
Posty: 36
Rejestracja: 22 kwie 2022, o 16:34
Płeć: Kobieta
wiek: 20
Podziękował: 12 razy

Graf

Post autor: xkatekx »

Zbiorem wierzchołków grafu \(\displaystyle{ G=(V,E)}\) jest zbiór \(\displaystyle{ V=P_2(X)}\) wszystkich 2-elementowych podzbiorów \(\displaystyle{ X=\left\{ 1,2,3,4,5\right\} }\). Jeśli \(\displaystyle{ A,B \in V}\) i \(\displaystyle{ A \neq B}\), to \(\displaystyle{ \left\{ A,B\right\} \in E}\) wtedy i tylko wtedy gdy \(\displaystyle{ A\cap B=\emptyset}\).
a) Ile wierzchołków i krawędzi ma graf \(\displaystyle{ G}\)?
b) Czy graf \(\displaystyle{ G}\) jest eulerowski?
c) Czy graf \(\displaystyle{ G}\) jest hamiltonowski?
d) Czy graf \(\displaystyle{ G}\) jest planarny?
Odpowiedź uzasadnij.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Graf

Post autor: kerajs »

Liczba wierzchołków: \(\displaystyle{ {5 \choose 2}=10 }\)
Wierzchołek z etykietą (a,b) jest połączony tylko z wierzchołkami o etykietach (c,d), (c,e) i (d,e) , więc każdy ma stopień 3.
Liczba krawędzi: \(\displaystyle{ \frac{10 \cdot 3}{2}=15 }\)
Nie jest eulerowski ze względu liczbę wierzchołków nieparzystego stopnia.
Nie ma cyklu Hamiltona ale ma ścieżkę Hamiltona, więc zdecyduj czy jest hamiltonowskim.
Posiada małą izomorfię z dwudzielną kliką \(\displaystyle{ K_{ 3,3}}\) więc nie jest planarny.

Dodano po 2 minutach 5 sekundach:
Ech, niepotrzebnie powyższe napisałem skoro wystarczyło zauważyć, że to graf Petersena.
ODPOWIEDZ