作者:
出版社:
简介:
片断:
CHAPTER1
Fundamentals
Thepurposeofthisintroductionistofamiliarisethereaderwiththebasic
conceptsandresultsofgraphtheory.Thechapterinevitablycontainsa
largenumberofdefinitionsandinordertopreventthereadergrowing
wearyweprovesimpleresultsassoonaspossible.Thereaderisnotexpected
tohavecompletemasteryofChapter1beforesamplingtherestofthe
book,indeed,heisencouragedtoskipaheadsincemostoftheterminology
isself-explanatory.Weshouldaddatthisstagethattheterminologyof
graphtheoryisfarfrombeingstandard,thoughthatusedinthisbookis
wellaccepted.
?Definitions
AgraphGisanorderedpairofdisjointsets(V,E)suchthatEisasubset
ofthesetofunorderedpairsofV.Unlessitisexplicitlystatedotherwise,we
consideronlyfinitegraphs,thatisVandEarealwaysfinite.ThesetVis
thesetofverticesandEisthesetofedges.IfGisagraphthenV=v(G)
isthevertexsetofGandE=E(G)istheedgeset.Anedge{x,y}issaidto
jointheverticesxandyandisdenotedbyxy.Thusxyandyxmeanexactly
thesameedge;theverticesxandyaretheendverticesofthisedge.IfxyeE(6)
thenxandyareadjacentorneighbouringverticesofGandtheverticesx
andyareincidentwiththeedgexy.Twoedgesareadjacentiftheyhave
exactlyonecommonendvertex.
Astheterminologysuggests,wedonotusuallythinkofagraphasan
orderedpair,butasacollectionofverticessomeofwhicharejoinedby
edges.Itisthenanaturalsteptodrawapictureofthegraph.Infact,some-
timestheeasiestwaytodescribeagraphistodrawit;thegraphG=
({1,2,3,4,5,6},{12,14,16,25,34,36,45,56})isimmediatelycomprehended
bylookingatFigure1.1.
WesaythatG'=(V',E')isasubgraphofG=(V,E)ifV'Vand
E'E.InthiscasewewriteG'G.IfG'containsalledgesofGthatjoin
twoverticesinV'thenG'issaidtobethesubgraphinducedorspannedby
V'andisdenotedbyG[v'].AsubgraphG'ofGisaninducedsubgraphif
G'=G(G')].IfV'=V,thenG'issaidtobeaspanningsubgraphofG.
TheseconceptsareillustratedinFigure1.2.
Weshalloftenconstructnewgraphsfromoldonesbydeletingoradding
someverticesandedges.IfWv(G)thenG-W=G[V\W]isthesub-
graphofGobtainedbydeletingtheverticesinWandalledgesincidentwith
them.SimilarlyifE'E(G)thenG-E'=(v(G),E(G)\E').IfW={w}
andE'={xy}thenthisnotationissimplifiedtoG-wandG-xy.
Similarly,ifxandyarenon-adjacentverticesofGthenG xyisobtained
fromGbyjoiningxtoy.