简介
片断：
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.
目录
chapter i
fundamentals
1. definitions
2. paths, cycles and trees
3. hamilton cycles and euler circuits
4. planar graphs
5. an application of euler trails to algebra
exercises
notes
chapter ii
electrical networks
1. graphs and electrical networks
2. squaring the square
3. vector spaces and matrices associated with graphs
exercises
notes
chapter iii
flows, connectivity and matching
1. flows in directed graphs
2. connectivity and menger's theorem
.3. matching
4. tutte's l-factor theorem
exercises
notes
chapter iv
extremal problems
1. paths and cycles
2. complete subgraphs
3. hamilton paths and cycles
4. the structure of graphs
exercises
notes
chapter v
colouring
1. vertex colouring
2. edge colouring
3. graphs on surfaces
exercises
notes
chapter vi
ramsey theory
1. the fundamental ramsey theorems
2. monochromatic subgraphs
3. ramsey theorems in algebra and geometry
4. subsequences
exercises
notes
chapter vii
random graphs
1. complete subgraphs and ramsey numbers--the use of the expectation
2. girth and chromatic number--altering a random graph
3. simple properties of almost all graphs--the basic use of probability
4. almost determined variables--the use of the variance
5. hamilton cycles--the use of graph theoretic tools
exercises
notes
chapter viii
graphs and groups
1. cayley and schreier diagrams
2. applications of the adjacency matrix
3. enumeration and polya's theorem
exercises
notes
subject index
index of symbols
fundamentals
1. definitions
2. paths, cycles and trees
3. hamilton cycles and euler circuits
4. planar graphs
5. an application of euler trails to algebra
exercises
notes
chapter ii
electrical networks
1. graphs and electrical networks
2. squaring the square
3. vector spaces and matrices associated with graphs
exercises
notes
chapter iii
flows, connectivity and matching
1. flows in directed graphs
2. connectivity and menger's theorem
.3. matching
4. tutte's l-factor theorem
exercises
notes
chapter iv
extremal problems
1. paths and cycles
2. complete subgraphs
3. hamilton paths and cycles
4. the structure of graphs
exercises
notes
chapter v
colouring
1. vertex colouring
2. edge colouring
3. graphs on surfaces
exercises
notes
chapter vi
ramsey theory
1. the fundamental ramsey theorems
2. monochromatic subgraphs
3. ramsey theorems in algebra and geometry
4. subsequences
exercises
notes
chapter vii
random graphs
1. complete subgraphs and ramsey numbers--the use of the expectation
2. girth and chromatic number--altering a random graph
3. simple properties of almost all graphs--the basic use of probability
4. almost determined variables--the use of the variance
5. hamilton cycles--the use of graph theoretic tools
exercises
notes
chapter viii
graphs and groups
1. cayley and schreier diagrams
2. applications of the adjacency matrix
3. enumeration and polya's theorem
exercises
notes
subject index
index of symbols
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
