Witam,
Mam taki problem:
Jak mając np, taką macierz sąsiadztwa:
| 0 2 1 2 |
| 2 0 1 1 |
| 1 1 0 1 |
| 2 1 1 0 |
Obliczyć ile ma krawędzi(oczywiscie bez rysowania tego grafu:) )?
Doszedlem do takiego wiosku, ze jest to graf prosty, spojny wiec ilosc krawedzi to polowa sumy stopni wszystkich krawedzi...
Nie ma jakiegos inego sposobu na obliczenie w/w problemu?
pozdrawiam
Jacek
Macierz sąsiedztwa, a ilość krawędzi
-
- Użytkownik
- Posty: 18
- Rejestracja: 28 sty 2006, o 19:38
- Płeć: Mężczyzna
- Lokalizacja: Olsztyn
- Pomógł: 2 razy
Macierz sąsiedztwa, a ilość krawędzi
Macierz sąsiedztwa grafu G = [aij] o wymiarze nxn, taka, ze wyraz aij jest równy liczbie krawedzi i,j nalezacych do E(G).
Dla mnie jest to graf o 4 wierzcholkach i 8 krawedziach:
masz krawedzie takie:
pomiedzy 1-2 - 2 krawedzie;
pomiedzy 1-3 - 1 krawedz;
pomiedzy 1-4 - 2 krawedzie;
pomiedzy 2-1 - 2 krawedzie; - ta sama krawedz co pomiedzy 1-2 wiec nie wliczasz;
pomiedzy 2-3 - 1 krawedz;
pomiedzy 2-4 - 1 krawedz;
pomiedzy 3-1 - 1 krawedz; - ta sama krawedz co pomiedzy 1-3 wiec nie wliczasz;
pomiedzy 3-2 - 1 krawedz; - ta sama krawedz co pomiedzy 2-3 wiec nie wliczasz;
pomiedzy 3-4 - 1 krawedz;
pomiedzy 4-1 - 2 krawedzie; - ta sama krawedz co pomiedzy 1-4 wiec nie wliczasz;
pomiedzy 4-2 - 1 krawedz; - ta sama krawedz co pomiedzy 2-4 wiec nie wliczasz;
pomiedzy 4-3 - 1 krawedz; - ta sama krawedz co pomiedzy 3-4 wiec nie wliczasz;
ogolny wniosek : Po macierzy sasiedztwa mozna dojsc do ilosci krawedzi grafu poprzez dodanie wszystkich elementow macierzy i podzielenie pzrez 2
(Dla grafu prostego)
Do tego mozna zobaczyc, czy graf jest prosty;
nasz akurat jest,bo na glownej pzrekatnej ma same 0 (Co oznacza, ze nie ma w nim petli);
Dla mnie jest to graf o 4 wierzcholkach i 8 krawedziach:
masz krawedzie takie:
pomiedzy 1-2 - 2 krawedzie;
pomiedzy 1-3 - 1 krawedz;
pomiedzy 1-4 - 2 krawedzie;
pomiedzy 2-1 - 2 krawedzie; - ta sama krawedz co pomiedzy 1-2 wiec nie wliczasz;
pomiedzy 2-3 - 1 krawedz;
pomiedzy 2-4 - 1 krawedz;
pomiedzy 3-1 - 1 krawedz; - ta sama krawedz co pomiedzy 1-3 wiec nie wliczasz;
pomiedzy 3-2 - 1 krawedz; - ta sama krawedz co pomiedzy 2-3 wiec nie wliczasz;
pomiedzy 3-4 - 1 krawedz;
pomiedzy 4-1 - 2 krawedzie; - ta sama krawedz co pomiedzy 1-4 wiec nie wliczasz;
pomiedzy 4-2 - 1 krawedz; - ta sama krawedz co pomiedzy 2-4 wiec nie wliczasz;
pomiedzy 4-3 - 1 krawedz; - ta sama krawedz co pomiedzy 3-4 wiec nie wliczasz;
ogolny wniosek : Po macierzy sasiedztwa mozna dojsc do ilosci krawedzi grafu poprzez dodanie wszystkich elementow macierzy i podzielenie pzrez 2
(Dla grafu prostego)
Do tego mozna zobaczyc, czy graf jest prosty;
nasz akurat jest,bo na glownej pzrekatnej ma same 0 (Co oznacza, ze nie ma w nim petli);