DSC00273 (5)

Elementy teorii grafów i sieci

Bohdan Korzon, WNT, Warszawa 1978, Mank Siwiak, Badania Operacyjne, OWPW1998.

Konstrukcja sieciowych modeli decyzyjnych, a w wielu przypadkach także ich rozwiązania, oparta jest na teorii grafów. Grafy pozwaląją przedstawiać w sposób bardzo poglądowy, jednocześnie wygodny dla operacji informatycznych, związki między obiektami w złożonych procesach produkcyjnych..

Definicja grafa:

Grafem nazywamy trójkę uporządkowaną G^m<W,U, Q>, w której fFjest zbiorem wierzchołków grafu, U zbiorem jego gałęzi, a Q jest relacją trój członową (2 cr WxUxW spełniającą warunki:

a)    dla każdej gałęzi u e U istnieje taka para wierzchołków x\y eW, że <x,u#>reQ,

b)    jeśli dla pewnej gałęzi u eU istnieją <x, u,y>eQ oraz <v, u, z>eQ, to albo jc«viy«*z łub **tijr«v.

Rodzaje gałęzi:

•    krawędzie — linia łączące odpowiednie wierzchołki

•    hild - strzałki łączące odpowiednie wierzchołki

•    pętłe — linie zamknięte wychodzące i wchodzące do tego samego wierzchołka.

Definicja:

Mówimy, że wierzchołekxeW i gałąź ue U są incydentne, jeśli istnieje wierzohołek yeW taki, że <są u,y>eQ hib <y, u, x> eQ.

Mówimy, że dwa wierzchołki są przyległe w grafie, jeżeli istnieje przynajmniej jedna g»łą* incydentna jednocześnie z obu tymi wierzchołkami.

Mówimy^le dwie gałęzie są przyległe, jeżeli istnieje przynajmniej jeden wierzchołek incydeniny jednocześnie z obu tymi gałęziami Macierzowe określenie grafit:

macierz incydencji wierzchołków i gałęzi A^mfay] (i^ml,2,,..,n, j^ml,2,...,m)

macierz przyległości wierzchołków R^m[ry] (ł,J^ml,2;...,n).

( macierz symetryczna, której elementy okrełlają liczbą gałęzi łączących odpowiednie pary wierzchołków grafit)

macierz przyległości gałęzi    B~[by] (i,j ^ml_t2,...,m)

macierz przejść    P^mlPvJ

(macierz, któnj elementy okrełlają liczbą luków łączących wierzchołek ł zj )

W zastosowaniach wykorzystuje się również binarną postać raacjerztf»