Spójność grafu
-
- Użytkownik
- Posty: 2
- Rejestracja: 24 mar 2017, o 23:33
- Płeć: Mężczyzna
Spójność grafu
Graf prosty o 21 wierzchołkach. Dla dowolnej pary wierzchołków \(\displaystyle{ x, y}\) zachodzi warunek \(\displaystyle{ d(x)+d(y) \ge 20}\). Czy graf jest spójny?
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Spójność grafu
Załóżmy, że nie jest spójny. To znaczy, że ma przynajmniej dwie spójne składowe. Któraś ze spójnych musi zawierać co najwyżej \(\displaystyle{ 10}\) wierzchołków. Jeżeli jest wśród nich spójna wielkości \(\displaystyle{ 1}\) to bierzemy wierzchołek z tej spójnej i dowolny inny (który ma co najwyżej \(\displaystyle{ 19}\) sąsiadów) - wtedy \(\displaystyle{ d(x) + d(y) \le 0 + 19 = 19}\), sprzeczność. Wpp. istnieje spójna, która ma więcej niż \(\displaystyle{ 1}\) i nie więcej niż \(\displaystyle{ 10}\) wierzchołków. Weźmy dowolne dwa wierzchołki z tej spójnej - wtedy \(\displaystyle{ d(x) + d(y) \le 9 + 9 = 18}\) - stopień każdego z tych wierzchołków nie może przekraczać wielkości spójnej minus \(\displaystyle{ 1}\), czyli \(\displaystyle{ 9}\), sprzeczność.
To znaczy, że jest spójny.
To znaczy, że jest spójny.
-
- Użytkownik
- Posty: 2
- Rejestracja: 24 mar 2017, o 23:33
- Płeć: Mężczyzna
Spójność grafu
No bo masz \(\displaystyle{ 21}\) wierzchołków. Czyli jak jedna ma \(\displaystyle{ 15}\) wierzchołków to kolejna ma co najwyżej \(\displaystyle{ 10}\) itd.alto de aitana pisze:Dlaczego, ktoras ze spojnych musi zawierac co najwyzej 10 wierzcholkow?