Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.2.SPÓJNOŚĆGRAFU
TwierdzenieKuratowskiego:
Jeżeliwgrafiekażdyzwęzłówstopnia2.igałęzieznimincydentnezastą-
pionezostanąjednągałęzią(usuniętezostanąwszystkiegałęzierozszerzone),
wówczaswarunkiemkoniecznymiwystarczającymplanarnościgrafujest,aby
tzw.pierwszyidrugigrafKuratowskiego.
K5
K3,3
(a)
(b)
Rys02050Grafy:pełnyopięciuwierzchołkach(K5)(a)orazpełnydwudzielny
osześciuwierzchołkach(K373)(b)
201060Grafyizomorficzne
Jeżeliistniejemożliwośćtakiegoprzyporządkowaniawdwóchgrafachpo-
szczególnychwierzchołków,żekażdejzgałęziwjednymgrafieodpowiadainna
gałąźzgrafudrugiego,mającetakąsamąparęodpowiadającychsobiewierzchoł-
ków(zobutychgrafów),tografytenazywamyizomorficznymi.Przykładgrafów
izomorficznych(G1orazG
!
str.49–50).
2020Spójnośćgrafu
ŚcieżkałączącawierzchołkiAiB–uporządkowanyzbiórgałęzi(ciąggałęzi
iwierzchołkówznimiincydentnych)taki,że:pierwszagałąźzezbioruincydentna
jestzwęzłemA,aostatniazwęzłemB.StopniewęzłówAiBsąrówne1,
astopniewszystkichpozostałychwęzłówincydentnychzgałęziamiścieżkisą
równe2.Dwiekolejnegałęzieztegozbiorumająjedenwspólnywęzeł.Danagałąź
występujewścieżcetylkojedenraz.
Długośćścieżki–toliczbagałęzijątworzących.
Grafspójny–tograf,wktórympomiędzydowolniewybranąparąwęzłów
istniejeścieżka.
Grafniespójny–totakigraf,wktórymmożnazezbioruwęzłówwybrać
dwa,pomiędzyktóryminiedasięutworzyćścieżki.
51
