Definitions ■A graph G=(V，E)consists of a set of vertices,V and a set of edges,E. Each edge is a pair (v,w),where v,we V.Edges are sometimes referred to as arcs.If the pair is ordered,then the graph is directed. Vertex wis adjacent to v if and only if (v,w)eE. In an undirected graph with edge iv w,wis adjacent to vand vis adjacent to w.Some times an edge has a third component,known as either a weight or a cost
Definitions ◼ A graph G=(V, E) consists of a set of vertices, V, and a set of edges, E. ◼ Each edge is a pair (v, w), where v, wV. Edges are sometimes referred to as arcs. If the pair is ordered, then the graph is directed. ◼ Vertex w is adjacent to v if and only if (v, w)E. In an undirected graph with edge {v, w}, w is adjacent to v and v is adjacent to w. Some times an edge has a third component, known as either a weight or a cost
Definitions A path in a graph is a sequence of vertices wi,w2, w3,...,Ww such that (wi W1)EEfor 1s/N.The length of such a path is the number of edges on the path,which is equal to /1. ■ We allow a path from a vertex to itself;if this path contains no edges,then the path length is 0. If the graph contains an edge (v,v)from a vertex to itself,then the path v,vis sometime referred to as a loop.The graphs we will consider will generally be loopless. A simple path is a path such that all vertices are distinct,except that the first and the last could be the same
Definitions ◼ A path in a graph is a sequence of vertices w1 , w2 , w3 , …, wN such that (wi , wi+1)E for 1i<N. The length of such a path is the number of edges on the path, which is equal to N-1. ◼ We allow a path from a vertex to itself; if this path contains no edges, then the path length is 0. ◼ If the graph contains an edge (v, v) from a vertex to itself, then the path v, v is sometime referred to as a loop. The graphs we will consider will generally be loopless. ◼ A simple path is a path such that all vertices are distinct, except that the first and the last could be the same
Definitions A cycle in a directed graph is a path of length at least 1 such that wi=w;this cycle is simple if the path is simple. For undirected graphs,we require that the edges be distinct;that is,the path u,v,win an undirected graph should not be considered a cycle,because (u, v and (v,u)are the same edge.In a directed graph, these are different edges,so it makes sense to call this a cycle. A directed graph is acyclic if it has no cycles
Definitions ◼ A cycle in a directed graph is a path of length at least 1 such that w1=wn ; this cycle is simple if the path is simple. ◼ For undirected graphs, we require that the edges be distinct; that is, the path u, v, u in an undirected graph should not be considered a cycle, because (u, v) and (v, u) are the same edge. In a directed graph, these are different edges, so it makes sense to call this a cycle. ◼ A directed graph is acyclic if it has no cycles
Definitions An undirected graph is connected if there is a path from every vertex to every other vertex.A directed graph with this property is called strongly connected.If a directed graph is not strongly connected,but the underlying graph(without direction to the arcs)is connected,then the graph is said to be weakly connected. A complete graph is a graph in which there is an edge between every pair of vertices
Definitions ◼ An undirected graph is connected if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected. If a directed graph is not strongly connected, but the underlying graph (without direction to the arcs) is connected, then the graph is said to be weakly connected. ◼ A complete graph is a graph in which there is an edge between every pair of vertices
Definitions In an undirected graph,the degree of a vertex is the number of edges connected to this vertex. In an directed graph,the outdegree of a vertex is the number of edges that start from this vertex,and the indegree is the number of edges that end at this vertex. ■ Examples of graphs:airport system,traffic flow, friendship
Definitions ◼ In an undirected graph, the degree of a vertex is the number of edges connected to this vertex. ◼ In an directed graph, the outdegree of a vertex is the number of edges that start from this vertex, and the indegree is the number of edges that end at this vertex. ◼ Examples of graphs: airport system, traffic flow, friendship