u v G = (V,E)
V is the vertex set.
Vertices are also called nodes and points.
E is the edge set.
Each edge connects two different vertices.
Edges are also called arcs and lines.
Directed edge has an orientation (u,v).
Graphs
u v Undirected graph => no oriented edge.
Directed graph => every edge has an orientation. Undirected edge has no orientation (u,v).
Undirected Graph
2 3 8 10 1 4 5 9 11 6 7
Directed Graph (Digraph)
2 3 8 10 1 4 5 9 11 6 7
Applications—Communication Network
2 3 8 10 1 4 5 9 11 6 7 Vertex = city, edge = communication link.
Internet connection. Vertices are computers. Send email from 1 to 7.
Each edge is of the form (u,v), u != v.
Number of such pairs in an n vertex graph is n(n-1).
Since edge (u,v) is the same as edge (v,u), the number of edges in a complete undirected graph is n(n-1)/2.
Number of edges in an undirected graph is <= n(n-1)/2.
Number Of Edges--Directed Graph
Each edge is of the form (u,v), u != v.
Number of such pairs in an n vertex graph is n(n-1).
Since edge (u,v) is not the same as edge (v,u), the number of edges in a complete directed graph is n(n-1).
Number of edges in a directed graph is <= n(n-1).
Vertex Degree
2 3 8 10 1 4 5 9 11 6 7 Number of edges incident to vertex.
degree(2) = 2, degree(5) = 3, degree(3) = 1
Sum Of Vertex Degrees
8 10 9 11 Sum of degrees = 2e (e is number of edges)
In-Degree Of A Vertex
2 3 8 10 1 4 5 9 11 6 7 in-degree is number of incoming edges
indegree(2) = 1, indegree(8) = 0
Out-Degree Of A Vertex
2 3 8 10 1 4 5 9 11 6 7 out-degree is number of outbound edges
outdegree(2) = 1, outdegree(8) = 2
Sum Of In- And Out-Degrees
each edge contributes 1 to the in-degree of some vertex and 1 to the out-degree of some other vertex
sum of in-degrees = sum of out-degrees = e,
where e is the number of edges in the digraph
Comments