Treść zadania

Rozwiązania

• 

  1 0

  antekL1 7.6.2017 (12:01)

  Powiedzmy, że ten graf jest niespójny i dzieli się na dwa grafy proste,
  mające odpowiednio k oraz n - k krawędzi.
  Pokażemy, że ilość krawędzi w tych grafach jest co najwyżej równa :
  (n - 1)(n - 2) / 2.
  
  Pierwszy graf zawiera k (k - 1) / 2 krawędzi [ więcej nie może, bo jest prosty ]
  Drugi graf zawiera co najwyżej (n - k)(n - k - 1) / 2 krawędzi.
  
  Obliczamy wyrażenie (funkcję)
  
  D(k) = (n - 1)(n - 2) / 2 - k (k - 1) / 2 - (n - k)(n - k - 1) / 2
  
  Użyłem programu, aby to poprzekształcać i uprościć, wychodzi:
  
  D(k) = (k - 1)(n - k - 1) / 2 = (-k^2 +nk - n + 1) / 2
  
  Oczywiście liczba k musi spełniać warunek: 0 < k < n
  
  Funkcja D(k) przedstawia parabolę w kształcie odwróconej litery U
  (bo współczynnik przy k^2 jest ujemny)
  mającą miejsca zerowe k1 = 1 oraz k2 = n - 1
  
  Aby funkcja D(k) była ujemna konieczne jest k < 1 lub k > n - 1
  co jest sprzeczne z założeniem, że 0 < k < n
  
  Wobec tego dla wszystkich dozwolonych k różnica liczby (n - 1)(n - 2) / 2
  i MAKSYMALNEJ ilości krawędzi w dwóch niespójnych grafach
  jest dodatnia lub co najwyżej zerowa gdy k = 1 [ wydzielamy jeden wierzchołek ]
  
  Jeśli dodamy choć jedną krawędź to NIE wystarczy krawędzi w obu grafach składowych razem, musimy połączyć te dwa grafy tworząc graf spójny.
  Koniec dowodu.
  ==========================
  
  W razie pytań pisz proszę na priv.

  Dodaj komentarz - Zgłoś nadużycie

  Zaloguj się lub załóź konto aby dodać komentarz.

  Dodaj