Każdy graf można przedstawić graficznie przyjmując, że każdej krawędzi przyporządkowujemy linię łączącą odpowiednie wierzchołki, każdemu łukowi -strzałkę łączącą odpowiednie wierzchołki, a każdej pętli linię zamkniętą, wychodzącą i wchodzącą do tego samego wierzchołka. Zadany powyżej graf ma postać przedstawioną na rys. 1.1.

Macierzowe określenie grafu

te”

Definicja incydencji

Rozważ my graf

G = <W, U, P>,

mówimy, ż e wierzchołek x∈ W i gałąź u ∈ U grafu G są incydentne wtedy i tylko wtedy, gdy istnieje wierzchołek y ∈ W, taki, że <x,u,y> ∈P lub

<y,u,x> ∈ P.

Definicja incydencji pozwała na macierzowe określenie grafu. Każdy graf o ponumerowanych wierzchołkach i gałęziach można jednoznacznie określić za pomocą pięciowartościowej macierzy incydencji A(G) określonej w następujący sposób:

A(G) = [a_ij]_nxm

i = 1, ..., n, gdzie n = |W| - liczność wierzchołków,

j = l, ..., m, gdzie m = |U| - liczność gałęzi,

gdzie:a_ij aelement macierzy przyjmujący jedną z pięciu wartości :

a _ij= α , gdy wierzchołek x₁ jest początkiem łuku, tzn., gdy istnieje

taki wierzchołek y, że

<X₁, u~‚y> E P a <y,u~,x₁> ~ P.

a_1~=f3, gdy wierzchołek x₁ jest końcem łuku uj, tzn., gdy istnieje

Rys. 1.1. Przykład graf u

---