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.
Minimalny zbiór pokrywający
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Minimalny zbiór pokrywający
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}\)
\(\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}\)