正在加载图片...
31.1 GraphsTwo vertices r, y of G are adjacent, or neighbours, if ry is an edgeadjacentof G. Two edges e + f are adjacent if they have an end in common. If allneighbourthe vertices of G are pairwise adjacent, then G is complete. A completecompletegraph on n vertices is a K"; a K3 is called a triangle.K"Pairwise non-adjacent vertices or edges are called independent.penateMore formally, a set of vertices or of edges is independent (or stable)if notwoof itselementsareadjacentLet G = (V,E) and G' - (V', E') be two graphs. We call G andG' isomorphic, and write G ~ G', if there exists a bijection p: V_ ViRwith ry e E p(r)p(y) e E' for all r,y e V. Such a map p is calledisomor-an isomorphism; if G = G', it is called an automorphism. We do notphismnormally distinguish between isomorphic graphs. Thus, we usually writeG - G' rather than G ~ G', speak of the complete graph on 17 vertices,and so on.A class of graphs that is closed under isomorphism is called a graphproperty. For example, 'containing a triangle' is a graph property: ifpropertyG contains three pairwise adjacent vertices then so does every graphisomorphic to G. A map taking graphs as arguments is called a graphinuariant if it assigns equal values to isomorphic graphs. The numberinvariantof vertices and the number of edges of agraph are two simple graphinvariants:thegreatestnumber of pairwise adjacent verticesisanother14G'1..423°.5GUG'G-G'GnG'. Union, difference and intersection; the vertices 2,3,4Fig. 1.1.2.induce (or span) a triangle in GUG' but not in GWe set GuG':=(VUV',EuE')and GnG':=(VnV',EnE')GnG!If GnG' = O, then G and G' are disjoint. If V'V and E'C E, then subgraphG' is a subgraph of G (and G a supergraph of G'), written as G' C GG'CGLess formally, we say that G contains G'. If G' G and G' + G, thenG' is a proper subgraph of GIf G' C G and G' contains all the edges ry e E with r, y e V', theninducecG' is an induced subgraph of G; we say that V'induces or spans G' in G,subgraph1.1 Graphs 3 Two vertices x, y of G are adjacent, or neighbours, if xy is an edge adjacent of G. Two edges e = f are adjacent if they have an end in common. If all neighbour the vertices of G are pairwise adjacent, then G is complete. A complete complete graph on n vertices is a Kn; a K3 is called a triangle. Kn Pairwise non-adjacent vertices or edges are called independent. More formally, a set of vertices or of edges is independent (or stable) independent if no two of its elements are adjacent. Let G = (V,E) and G = (V , E ) be two graphs. We call G and G isomorphic, and write G G , if there exists a bijection ϕ: V → V with xy ∈ E ⇔ ϕ(x)ϕ(y) ∈ E for all x, y ∈ V . Such a map ϕ is called an isomorphism; if G = G , it is called an automorphism. We do not isomorphism normally distinguish between isomorphic graphs. Thus, we usually write G = G rather than G G , speak of the complete graph on 17 vertices, and so on. A class of graphs that is closed under isomorphism is called a graph property. For example, ‘containing a triangle’ is a graph property: if property G contains three pairwise adjacent vertices then so does every graph isomorphic to G. A map taking graphs as arguments is called a graph invariant if it assigns equal values to isomorphic graphs. The number invariant of vertices and the number of edges of a graph are two simple graph invariants; the greatest number of pairwise adjacent vertices is another. G ∪ − G G ∩ 1 2 3 4 5 G 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 G G G G Fig. 1.1.2. Union, difference and intersection; the vertices 2,3,4 induce (or span) a triangle in G ∪ G but not in G We set G ∪ G := (V ∪ V , E ∪ E ) and G ∩ G := (V ∩V , E ∩ E ). G ∩ G If G ∩ G = ∅, then G and G are disjoint. If V ⊆ V and E ⊆ E, then subgraph G is a subgraph of G (and G a supergraph of G ), written as G ⊆ G. G ⊆ G Less formally, we say that G contains G . If G ⊆ G and G = G, then G is a proper subgraph of G. If G ⊆ G and G contains all the edges xy ∈ E with x, y ∈ V , then G is an induced subgraph of G; we say that V induces or spans G in G, induced subgraph