Matematyka dyskretna, zadanie nr 4664

Autor	Zadanie / 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: 8070	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