Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
4
1.Defnicjagrafuiprzykładyzastosowań
Kołon-wierzchołkowe(n;4)W
njestgrafem,wktórymjedenwierzchołekjest
stopnian-1,apozostałewierzchołkisąwierzchołkamistopnia3(rys.1.3f).
Wachlarzn-wierzchołkowy(n;3)F
njestgrafemojednymwierzchołkustop-
nian-1,n-3wierzchołkachstopnia3orazdwóchwierzchołkachstopnia2.
Wachlarzotrzymujesiępoprzezusunięciejednejkrawędzileżącejnaobwodzie
koła(rys.1.3g).
KrataL
k,m,l;2,m;2jestgrafemozbiorzewierzchołków{1,2…,l}´
{1,2…,m}.Pomiędzywierzchołkami(i
1,j
1)i(i
2,j
2)istniejekrawędźwtedyitylkowte-
dy,gdy½i
1-i
2½+½j
1-j
2½=1.Przykładkratyol=2,m=3przedstawiarys.1.3h.
Rys.1.3.Przykładyniektórychgrafów:a)ścieżkaniezorientowanaP
naP
g)wachlarzF
5;c)cyklniezorientowanyC
6;h)krata2´3
5;d)cyklzorientowanyC
5;e)gwiazdaK
5;b)ścieżkazorientowa-
1,5;f)kołoW
6;
AbyzachęcićCzytelnikadogłębszegozainteresowaniagrafami,wdalszym
tekścieprzedstawimykilkanaścieprostychproblemówilustrującychzastosowania
grafówdomodelowaniaianalizyzjawiskorazprocesów.Przytoczoneprzykłady
niewyczerpująoczywiściebogactwazastosowań.Zapierwszyimpulsdopowstania
teoriigrafówjakodziałukombinatorykiuważasięproblemmostówkrólewieckich
sformułowanyirozwiązanyprzezLeonardaEulera.Niemalwszystkieksiążkizaj-
mującesięgrafamirozpoczynająsięodzacytowaniategoproblemu.Wtejksiążce
