logowanie

matematyka » forum » studia » zadanie

Matematyka dyskretna, zadanie nr 4664

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / Rozwiązanie

brightnesss
postów: 113
2016-06-06 21:38:12

Pokazać, że jeśli e(G)>${n-1 \choose 2}$ to graf G jest spójny.


tumor
postów: 8085
2016-06-08 09:40:34

graf, który nie jest spójny, ma najwyżej tyle krawędzi, ile dwie kliki (przemyśl)

jeśli graf ma n wierzchołków, to możemy rozważyć klikę o n-k wierzchołkach i klikę o k wierzchołkach, mają w sumie krawędzi
${n-k \choose 2}+{k \choose 2}
$
jeśli mamy dwie kliki o różnej ilości wierzchołków, a z kliki o mniejszej ilości wierzchołków usuniemy jeden i przełożymy do kliki o większej ilości (i uzupełnimy krawędzie), to ilość krawędzi w sumie wzrośnie.
Zatem dwie kliki mają najwięcej krawędzi dla k=1, jest ich wtedy ${n-1 \choose 2}+0$


strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 15 drukuj