Matematyka dyskretna, zadanie nr 1907
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
kasia1020 post贸w: 1 |  2014-01-14 15:29:39Korona 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