logowanie

matematyka » forum » forum zadaniowe - uczelnie wyższe » zadanie

Matematyka dyskretna, zadanie nr 1907

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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





© 2019 Mariusz Śliwiński      o serwisie | kontakt   drukuj