Graficele si matrici
Să - grafic cu noduri și. Construim o matrice pătrată de comandă, în care elementul de la intersecția numărul rândului și coloanei la un număr, definit după cum urmează:
Se numește matricea de adiacenta a graficului. matricea de adiacență pot fi construite pentru un grafic direcționat și nedirijat, și pentru grafice cu bucle. Grafic obișnuit are două caracteristici: din cauza lipsei de bucle pe diagonala principală sunt zero, precum și graficul este neorientat, atunci matricea este simetrică față de diagonala principală. Invers, ordinea fiecărei matrice pătratică formată din unu și zero și având aceste două proprietăți corespunde unui grafic obișnuit cu setul de noduri.
Alte matrice. asociate cu graficul - este matricea de incidență. Pentru a construi noduri Enumerate de numere întregi de la 1 până la, și marginile - numerele de la 1 la. matrice de incidență are rânduri și coloane, iar elementul său este egal cu 1 dacă nodul cu numărul de incidente de margine cu un număr, altfel este zero. Fig. 1.7 prezintă un grafic cu vârfuri etichetate și muchii și matricea de adiacență și incidență.
Pentru o matrice grafic incidență direcționată definit oarecum diferit: element al acesteia este 1 dacă nodul este partea de start, și este, dacă este capătul nervurii, și este, în cazul în care acest nod și nu această margine incident reciproc.
grafice ponderate
De multe ori, mai ales atunci când graficele sunt folosite pentru a modela sisteme de lumea reală, vârfurile lor, sau coaste, sau ambele, iar altele sunt atribuite anumite numere. Natura acestor numere pot fi cele mai diverse. De exemplu, în cazul în care graficul este un model al rețelei feroviare, numerele atribuite la marginea poate indica lungimea secțiunii între cele două stații, sau compoziția de greutate mai mare, care este admisibil pentru această secțiune a rutei, sau numărul mediu de trenuri care trec prin această zonă în timpul zilei și m n. Oricare ar fi semnificația acestor numere, există o tradiție să le numim greutăți. un grafic cu un anumit greutăți Vertex sau coaste - grafic ponderate.
izomorfism
Fig. 1.8 prezintă două grafice cu același set de noduri. La o inspecție mai atentă s-ar putea găsi că este coloane diferite - de pe stânga există un avantaj în lege nu există o astfel. În același timp, dacă nu acorde atenție la numele vârfurilor, aceste grafice sunt clar aranjate în același mod: fiecare dintre ele - o serie de patru noduri. În multe cazuri, structura studiului grafice nume sau un număr de noduri nu joacă nici un rol, și astfel de coloane, dintre care unul se obține din celălalt prin redenumirea noduri mai convenabil ar fi considerat la fel. Pentru ca se poate face „în mod legal“, introduce conceptul de grafic izomorfism.
Definiția. Conți și sunt izomorfe. în cazul în care există o bijectie pe platoul de filmare, astfel încât, dacă și numai dacă. Afișarea în acest caz se numește un izomorfism al graficului pe grafic.
Faptul că graficele sunt izomorfe, și este scris ca :.
Pentru graficele prezentate în Fig. 1.8. izomorfism este, de exemplu, afișaj. dat de tabelul de mai jos: