Matematyka.pl

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 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);