have a number 5 b or each vertex hs 12
❖ Definition 8: Graphs that have a number assigned to each edge or each vertex are called weighted graphs ❖ weighted digraphs
o Definition 9: The graph G(V,E) is s caned a subgraph of G(vE) If Vcv and EcE. If V=V, then G(,E) is said to be a spanning subgraph. v2 4 (a)G (b)subgraph G (spanning subgraph G
❖ Definition 9: The graph G'(V',E') is called a subgraph of G(V,E) If V'V and E'E. If V'=V, then G'(V,E') is said to be a spanning subgraph
Definition 10: If G(V,E) contains all edges of G that ioin two vertices in V then g is called the induced subgraph by v'cv and is denoted b G(V") go induced subgraph by ( v1v2 v4, v5 induced subgraph by IVi,V2, Va,v5
❖ Definition 10: If G'(V',E') contains all edges of G that join two vertices in V' then G' is called the induced subgraph by V'V and is denoted by G(V'). ❖ induced subgraph by {v1 ,v2 ,v4 ,v5 }
Definition 11: The complement of a graph g is the graph(denoted G) with the same vertex set but whose edge set consists of the edges not present in G(i.e, the complement of the edge set of G with respect to all possible edges on the vertex set of g) K
Definition 11: The complement of a graph G is the graph (denoted G ) with the same vertex set but whose edge set consists of the edges not present in G (i.e., the complement of the edge set of G with respect to all possible edges on the vertex set of G)
8G-v, or G-iv .o When we remove a vertex v from a graph, we must remove all edges incident with the vertex v When a edge is removed from a graph, without removing endpoints of the edge G
❖ G-v, or G-{v} ❖ When we remove a vertex v from a graph, we must remove all edges incident with the vertex v. ❖ When a edge is removed from a graph, without removing endpoints of the edge
Adjacency matrices and Incidence matrices 4 Definition 12: Let G(V,E) be a graph of non-multiple edge where vn. Suppose that v1,v2,,n are the vertices. The adjacency matrix A of G, with respect to this listing of the vertices, is the nxn zero-one matrix with 1 as its (i,jth entry when vi and vi are adjacent, and 0 as its (i,jth entry when they are not adjacent. In other words, If its adjacency matrix is A=lail, then 扩f, v is an edge of g otherwise
Adjacency matrices and Incidence matrices ❖ Definition 12: Let G(V,E) be a graph of non-multiple edge where |V|=n. Suppose that v1 ,v2 ,…,vn are the vertices. The adjacency matrix A of G, with respect to this listing of the vertices, is the nn zero-one matrix with 1 as its (i,j)th entry when vi and vj are adjacent, and 0 as its (i,j)th entry when they are not adjacent. In other words, If its adjacency matrix is A=[aij], then = otherwise i f v v i s an edge of G a i j i j 0 1 { , }
g Let G(v,E) be an undirected graph. Suppose that v1 v2,-.,Vn are the vertices and el, e2,.,e are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the nxm matrix M=miil, where when edge e is incident with y otherwise
❖ Let G(V,E) be an undirected graph. Suppose that v1 ,v2 ,…,vn are the vertices and e1 ,e2 ,…,em are the edges of G. Then the incidence matrix with respect to this ordering of V and E is the nm matrix M=[mij], where = otherwise when edge e i s incident withv m j i i j 0 1
00 0 010100 011010 图C 000000 e3 et es e6e, e8 1000 000 1000111 00000 011000 v00011110 aoe3
0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 5 4 3 2 1 1 2 3 4 5 6 7 8 v v v v v e e e e e e e e
Quotient graph Definition 13: Suppose G(VE) is a graph and R is a equivalence relation on the set V. we construct the quotient graph gR in the follow way. The vertices of GR are the equivalence classes of v produced by r If v and w are the equivalence classes of vertices v and w of G, then there is an edge in g between v and w if some vertex in v] is connected to some vertex in w in the graph G
❖Quotient graph ❖ Definition 13: Suppose G(V,E) is a graph and R is a equivalence relation on the set V. We construct the quotient graph GR in the follow way. The vertices of GR are the equivalence classes of V produced by R. If [v] and [w] are the equivalence classes of vertices v and w of G, then there is an edge in GR between [v] and [w] if some vertex in [v] is connected to some vertex in [w] in the graph G
5.2 Paths and circuits .8.5.2.1 Paths and circuits % Definition 14: Let n be a nonnegative integer and g be an undirected graph. A path of length n from u to y in G is a sequence of edges elsey,en of G such that e=vo=u, V1, e2=v1,V2,,en=vn-1,Vn=v), and no edge occurs more than once in the edge sequence. When G is a simple graph, we denote this path by its vertex sequence u=vo V1.Vn-V. A path is called simple if no vertex appear more than once. A circuit is a path that begins and ends with the same vertex. A circuit is simple if the vertices V1,V2,.,Vn-I are all distinct
5.2 Paths and Circuits ❖5.2.1 Paths and Circuits ❖ Definition 14: Let n be a nonnegative integer and G be an undirected graph. A path of length n from u to v in G is a sequence of edges e1 ,e2 ,…,en of G such that e1={v0=u,v1 }, e2={v1 ,v2 },…,en={vn-1 ,vn=v}, and no edge occurs more than once in the edge sequence. When G is a simple graph, we denote this path by its vertex sequence u=v0 ,v1 ,…,vn=v. A path is called simple if no vertex appear more than once. A circuit is a path that begins and ends with the same vertex. A circuit is simple if the vertices v1 ,v2 ,…,vn-1 are all distinct