Informatyka studia dzienne - WMI, WMID, UAM, Uniwersytet im. Adama Mickiewicza w Poznaniu

11:W-MAD-1/071206/0

Posted by basik in Wykłady - gr. 1, ... | 12.06.2007 - 08:15

Wykład prowadził dr Jerzy Jaworski
______________________________________________________________
PODSTAWOWE POJĘCIA TEORII GRAFÓW
______________________________________________________________

Graf - zbiór punktów (wierzchołków), i połączeń między nimi (krawędzi)

V - zbiór wierzchołków grafu (musi być niepusty)
E - zbiór krawędzi grafu

$e \in E$

$\psi :E \longrightarrow V^{2}$ - funkcja incydencji

$V^{2}$ - podzbiory 2-elementowe ze zbioru V (dopuszczalne pseudozbiory)

$\psi$ - funkcje incydencji (przyporządkowuje krawędzi jej wierzchołki)
$\psi ( e_{1})=\lbrace 1,2\rbrace$

$G=<V,E,\psi>$ - graf, czyli zb. wierzch., zb. krawędzi i funkcja incydencji

incydencja - zależność między końcem krawędzi a krawędzią

krawędź wielokrotna - dwa punkty połączone są co najmniej dwiema krawędziami

pętla - krawędź zaczynająca i kończąca się w tym samym punkcie

krawędź nieskierowana - krawędź “dwukierunkowa”
graf skierowany - graf posiadający krawędzie skierowane

Każdą relację dwuargumentową można przedstawić jako graf:

relacja zwrotna - pętla w każdym wierzchołku
relacja przechodniości - $(A\rightarrow B )\wedge ( B\rightarrow C)\rightarrow (A\rightarrow C)$

graf prosty - graf bez pętli krawędzi wielokrotnych

grafy identyczne - zbiory wierzchołków, zbiory krawędzi i funkcje incydencji są takie same

grafy izomorficzne (nieoznaczone) - po wymazaniu nazw wierzchołków i nazw krawędzi można je przedstawić tym samym grafem

stopień wierzchołka $d_G(v)$ - liczba krawędzi incydentnych z danym wierzchołkiem v (pętla liczy się podwójnie)

$\delta(G)$ - najniższy stopień w grafie
$\Delta(G)$ - najwyższy stopień w grafie

$\nu(G) = | V(G)|$ - liczba wierzchołków w grafie
$\epsilon(G) = | E(G)|$ - liczba krawędzi w grafie

$\sum_{v \in V(G)} d_G(v)=2 \epsilon (G)$
Suma stopni wszystkich wierzchołków jest równa podwojonej liczbie krawędzi

wierzchołek izolowany - wierzchołek o stopniu 0
wierzchołek wiszący - wierzchołek o stopniu 1

graf planarny - można go narysować w takiej postaci, że krawędzie nie będą się przecinać

graf skończony - zb. V i E są zbiorami skończonymi

$G^{c}$ - dopełnienie grafu prostego G

graf i jego dopełnienie mogą być izomorficzne - np. pięciokąt i pentagram

graf trywialny - graf składający się tylko z jednego wierzchołka

graf pusty - graf nie posiadający krawędzi
graf pełny - graf prosty o wszystkich możliwych krawędziach jednokrotnych

Problem wędrującego komiwojażera: jak przejść przez wszystkie wierzchołki dokładnie raz i wrócić do punktu wyjścia.

cykl Hamiltona - przejście przez wszystkie wierzchołki tylko 1 raz (n-1)(n-2)(n-3)…1=(n-1)!

KOMPUTEROWE PRZEDSTAWIENIE GRAFU

1) Macierz przyległości dla grafu nieskierowanego

Jeśli dwa punkty są połączone krawędzią, to wartość danego rekordu macierzy wynosi 1, jeśli nie 0.
Jeśli macierz jest symetrycyna względem głównej przekątnej, to wszystkie krawędzie są nieskierowane.

2) Macierz incydencji

Jeśli krawędź jest incydentna do wierzchołka, to wartość rekordu wynosi 1, gdy nie jest incydentna 0, pętla liczy się podwójnie, więc w takim przypadku rekord jest równy 2.