Bardzo proszę o pomoc, bo nie mogę znaleźć takiego twierdzenia albo obserwacji.
Jaki warunek musi spełniać macierz przyległości, aby gwarantować (WKKW) spójność grafu?
Znam tylko twierdzenie, że właściwy graf niezorientowany \(\displaystyle{ G}\) o \(\displaystyle{ n}\) węzłach i o liczbie pojedynczych krawędzi większej niż \(\displaystyle{ \frac{1}{2} \cdot (n-1) \cdot (n-2)}\) jest spójny.
Czyli mam zsumować wszystkie jedynki w macierzy przyległości, podzielić przez 2 i porównać z
\(\displaystyle{ \frac{1}{2} \cdot (n-1) \cdot (n-2)}\) ?? Jak jest więcej to graf jest spójny WKKW?
Jaka macierz przyległości aby WKKW na spójny graf
-
- Użytkownik
- Posty: 4
- Rejestracja: 16 gru 2014, o 18:45
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
Jaka macierz przyległości aby WKKW na spójny graf
Ostatnio zmieniony 18 gru 2014, o 16:29 przez Qń, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Jaka macierz przyległości aby WKKW na spójny graf
Pierwsze, co mi do głowy przychodzi, to nieredukowalność macierzy incydencji. To pojęcie możesz znaleźć , a jego związek z grafami