Matematyka dyskretna, zadanie nr 4664
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
brightnesss post贸w: 113 |  2016-06-06 21:38:12Pokaza膰, 偶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