3582327591

PODSTAWOWE DEFINICJE TEORII GRAFÓW

Definicja 1

Grafem skończonym G nazywamy skończony zbiór punktów {Vi, i = 1, N K zwanych wierzchołkami i skończony zbiór linii ^U;, i = I, Mr\ zwanych krawędziami takimi, że każda krawędź ma dwa (niekoniecznie różne) wierzchołki jako jej punkty końcowe oraz nie przechodzi ona przez inne wierzchołki. Mówimy, że krawędź jest incydentna (powiązana) z wierzchołkiem, jeśli jest on jednym z jej końców.

Definicją 2

Graf G nazywamy skierowanym, jeśli każda jego krawędź ma określoną orientację. Zorientowana krawędź „wychodzi” z wierzchołka, który jest jej początkiem i „wchodzi” do wierzchołka, która jest jej końcem lub inaczej - jest względem obu wierzchołków dodatnio i ujemnie incydentna.

Definicją 3

Graf G jest grafem spójnym, jeśli nie ma wierzchołków izolowanych, tzn. wierzchołków, z których nie można przejść po krawędziach grafu do dowolnego innego wierzchołka. Na rys. 1 przedstawiono graf spójny, niespójny oraz graf spójny skierowany.

Definicja 4

Dwa grafy są izomorficzne jeśli:

1.    jest wzajemnie jednoznaczna odpowiedniość między zbiorami wierzchołków,

2.    jest wzajemnie jednoznaczna odpowiedniość między ich zbiorami krawędzi,

3.    zachowana jest orientacja krawędzi dla grafów zorientowanych.