Cunoștințe, prelegere, grafice de prezentare, atingere și conectivitate

Matricea (tabelul) de contiguitate

Definiția 9.5. Matricea de adiacență a unui grafic orientat (sau nedirecționat) G = (V, E) cu n noduri și V = O matrice booleană AG de dimensiune n x n cu elemente

Matricea incidenței

Definiția 9.6. Matricea de incidență a unui grafic orientat (sau nedirecționat) G = (V, E) cu n noduri și V = și margini m E = 1. em> este o matrice BG de dimensiune n x m cu elemente

Liste de contiguitate

Definiție 9.7. Fie G = (V, E) un grafic orientat. v este un vârf din V. Lista de contiguitate Lv pentru vârful v include toate vârfurile adiacente. și anume

Reprezentarea graficului G = (V, E) cu n noduri și V = cu ajutorul listelor de contiguitate constă în liste de contiguitate a tuturor nodurilor: Lv1. Lv2. Lvn.

Dimensiunea acestei reprezentări este comparabilă cu suma numărului de vârfuri și marginile graficului. Ea facilitează mișcarea de-a lungul marginilor de la vârf la vecinii săi. În programe, liste de contiguitate sunt reprezentate de structuri de listă. care sunt ușor de implementat în toate limbile de programare.

Exemplul 9.1. Luați în considerare următorul grafic G = (V, E):