Minimalny zbiór pokrywający

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Kate2410

Minimalny zbiór pokrywający

Post autor: Kate2410 »

Wskaż minimalny zbiór pokrywający dla poniższych grafów:
a)\(\displaystyle{ W _{n}, n \ge 3 }\) (koło \(\displaystyle{ W _{n} }\) czyli graf powstały z cyklu\(\displaystyle{ C _{n} }\) poprzez dodanie nowego wierzchołka i połączenie go ze wszystkimi wierzchołkami cyklu \(\displaystyle{ C _{n} }\))
b) graf Petersena,
c) hiperkostka \(\displaystyle{ Q _{n} }\).
Dla grafu \(\displaystyle{ W _{n} }\)uzasadnij swój wybór.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Minimalny zbiór pokrywający

Post autor: arek1357 »

Po pierwsze nie do końca wiadomo o jakie pokrycie Ci biega czy krawędziowe czy wierzchołkowe, ale zabezpieczając się na tę ewentualność mamy dwa wzorki:

\(\displaystyle{ pw+nw=n \wedge pk+nk=n}\)

\(\displaystyle{ pw }\) - najmniej liczny podzbiór wierzchołków, taki, że każda krawędź jest incydentna z co najmniej jednym z nich...

\(\displaystyle{ nw }\) - najliczniejszy podzbiór wierzchołków, w którym żadne dwa nie są sąsiednie, czyli żadne dwa nie są połączone krawędzią...

\(\displaystyle{ pk}\) - najmniej liczny podzbiór krawędzi, taki, że każdy wierzchołek jest incydentny z co najmniej jedną z nich...

\(\displaystyle{ nk}\) - najliczniejszy podzbiór krawędzi, w którym żadne dwie nie są incydentne, czyli właśnie najliczniejsze skojarzenie w grafie...

\(\displaystyle{ n}\) - liczba wierzchołków w grafie...

narysuj sobie graf np petersena wymazuj punkty i krawędzie aż otrzymasz odpowiedź , lub inny graf...

Dodano po 17 minutach 37 sekundach:
Jeżeli chodzi o pokrycie krawędziowe w grafie petersena powinno raczej być:

\(\displaystyle{ 5+5=10}\)

Dodano po 25 minutach 54 sekundach:
A hiperkostka jest grafem dwudzielnym

Dodano po 4 minutach 46 sekundach:
A dla grafw dwudzielnych masz:

\(\displaystyle{ nk=pw \wedge nw=pk}\)
ODPOWIEDZ