Podaj stopień minimalny oraz liczbę krawędzi w grafie poaw: X = {1,2,3, ..., 9} G = (V, E) V − zbiór wszystkich 3−elem. pozdbiorów zbioru X (wyliczyłem, że jest ich 84. 9 po 3) E − zbiór krawędzi takich, że u,v ∊ E ⇔ |u ∩ v| = 1 Ile wynosi stopień minimalny w tym grafie? Ile ten graf ma krawędzi? Czy graf jest dwudzielny? Prosiłbym o jakieś proste wyjaśnienie. Pozdrawiam.
17 sty 10:53
Adamm:
 
nawias
6
nawias
nawias
2
nawias
 
biorąc konkretny wierzchołek 'u' tego grafu, mamy 3*
wierzchołków 'v' które spełniają
  
warunek |u ∩ v| = 1
 
nawias
9
nawias
nawias
3
nawias
 
nawias
6
nawias
nawias
2
nawias
 
mnożąc to razy ilość wierzchołków otrzymamy 3*
*
, ale przez 2
   
bo liczyliśmy podwójnie
 
 
nawias
9
nawias
nawias
3
nawias
 
nawias
6
nawias
nawias
2
nawias
 
3*
*
   
 
graf ma więc

krawędzi
 2 
17 sty 12:03
poaw: Dzięki, taka ma być odpowiedź. A skąd się bierze 3 * 6 po 2? Mógłbyś to wyjaśnić?
17 sty 12:15
Adamm: u = {a, b, c}, a, b, c∊{1, 2, ..., 9}, prawda |u ∩ v| oznacza że jeden z 'a', 'b', 'c' jest wspólnym punktem, a resztę musimy dobrać z innych '3', bo wybieramy jeden z 'a', 'b', 'c'
nawias
6
nawias
nawias
2
nawias
 
, bo wybieramy dwa punkty z {1, 2, ..., 9}, różne od 'a', 'b', 'c'
 
17 sty 12:17
Adamm: |u ∩ v| = 1
17 sty 12:18
poaw: Rozumiem. A z krawędziami? To jest po prostu to samo tylko razy ilość wierzchołków i przez 2 bo sie powtarzają?
17 sty 12:19
poaw: Dzięki wielkie!
17 sty 12:20