Matematyka dyskretna, zadanie nr 1907
ostatnie wiadomości | regulamin | latex
Autor | Zadanie / Rozwiązanie |
kasia1020 postów: 1 | 2014-01-14 15:29:39 Korona grafów udowodnić twierdzenie: Niech G i H będą dowolnymi grafami.Wtedy $\gamma$ (G$\circ$H)=|V(G)|,gdzie$ \gamma$ oznacz liczbę dominowania Wiadomość była modyfikowana 2014-01-14 15:30:07 przez kasia1020 |
tumor postów: 8070 | 2016-07-31 21:43:14 Wystarczy zauważyć, że V(G) jest zbiorem dominującym, a każdy inny zbiór dominujący ma nie mniejszą moc. Oczywiście w koronie grafów $G\circ H$ każdy wierzchołek każdej kopii H ma sąsiada z V(G) oraz każdy wierzchołek G należy do V(G). Czyli V(G) jest zbiorem dominującym. Poindeksujmy kopie grafu H jako $H_i$ po $i\in V(G)$. Wtedy oczywiście zbiory $V(\{i\}\cup H_i)$ są rozłączne, a skoro wierzchołki z $H_i$ są nie są połączone krawędziami z żadnym wierzchołkiem zbioru $\bigcup_{j\neq i}V(\{j\} \cup H_j)$, to albo $i$ jest w zbiorze dominującym, albo któryś z wierzchołków grafu $H_i$ jest w zbiorze dominującym. Wobec tego, że zbiorów $V(\{i\}\cup H_i)$ jest dokładnie $\mid V(G) \mid$, to zbiór dominujący nie może mieć mniejszej mocy. |
strony: 1 |
Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj