A graph consists of a set of vertices and a set of edges. A vertex is usually denoted by a small circle while an edge is just a line drawn between two vertices. The diagram Graph #1 is a graph consisting of four vertices and three edges. This graph is called an undirected graph as all the edges have no direction(undirected edges). Graphs where undirected edges join the same the vertex are called Multi-edge graphs. This discussion will be confined to only simple graphs.
In graph #1, we can denote all the vertices by the set V1= { A,B,C,D}. The set of all edges can be denoted by E1={m,n,p}. This graph can then be denoted by G1. To be more explicit and to emphasize that the graph is composed of a vertex and edge sets, G1 can be writen as G1( V1, E1). The G1( V1, E1) can also be written more explicitely as G1( {A,B,C,D}, {m,n,p}).
In an undirected graph, the degree of a node in a graph is the total number of edges that are incident on the node. For instance, in the G1 graph , the degree of node A is 2, while the degree of node D is zero. The total sum of all degrees of an undirected graph is equal to twice the number of edges. This is sometimes refered to as the Hand shaking Lemma. The proof is simply that every edge joins two nodes and increases the degree of each node by one. So, each edge increases the graphs total degree sum by two. It is called the Hand Shaking Lemma as it can be used to to solve the following problem. A group of people meet for the first time at a party. During the party, they mingle and meet others. Whenever one person meets another for the first time, they give each other a hand shake. At the end of the party, every person is asked the total number of handshakes he(or she) has given. The problem is to find find the total unique first time meetings. By using the the Hand Shaking Lemma, we can see that the total unique meetings is just the total number of handshakes divided by two. For Example, in G1 , if the vertices represents different people and each edge represents a hand shake, the total number of unique meetings is three, while the total count of all the handshakes that each person has given is six.
A subgraph of a graph is a new graph that contains a subset of the vertices and edges from the original graph. Every edge must still join nodes of the new graph. There is no such thing as a half edge. For instance the graph ({ A,B,D},{n} ) is a subgraph of G1. A subgraph can be the empty graph ( { }, { } ).
A sequences of edges and vertices that can be traveresed to go from one vertex to that of another is called a path. For instance, the path to go from vertex B to vertex C can be denoted by the sequence (B,n,A,m,C). Another path could be (B,n,A,n,B,p,C). Notice that this new path does a wasted trip to A and then back to B. To remove these wasted type paths, a Simple Path is a path such that no vertex or edge is found in the path sequence twice. Hence, in graph G1, the only two simple paths from B to C are (B,p,C) and (B,n,A,m,C). If a graph contains two nodes such that there are two distinct simple paths between one node and another, then the graph is said to contain a cycle. For instance, the graph G1 contains a cycle. If a graph does not contain a cycle, than it is called an acyclic graph. The length of a path is the total number of edges in a path sequence. For instance, the path sequence (A,m,C,p,B,n,A) has a path length of 3. Since the it starts and ends at the same vertex, the path is a cycle. A circuit is a path where the start vertex and destination vertex are the same.
A path in a graph is called an Euler Path, if the path contains every edge of the original graph. A path is called an Euler Circuit, if the path is an Euler Path that is a circuit. A Hamiltonian path is a path that in a graph that has all of the vertices of the graph. A Hamiltonian Circuit is an Hamiltonian path which is a circuit.
A connected graph is one in which every vertex can be reached using some path from every other vertex. A graph that is not connected is called a disconnected graph. As we cannot reach vertex D from any other vertex in graph G1, the graph is not connected. It is a disconnected graph. An acyclic connected graph is called a free tree. If a subgraph of a connected graph is a tree that still connects all the vertices of the original graph, then the tree is called a spanning tree.
A directed graph is one in which all the edges are directed. The graph #2 is a directed graph. Unlike undirected graphs, a directed graph may contain edges which start and end at the same vertex. The edge p is an example of such an edge(a self loop). But no two edges can be drawn with the same source and destination vertices. Symbolically, a directed graph is represented the same way as an undirected graph. For example, Graph #2 can be represented symbolically as G2=G2( { A,B,C,D } , { p,q,r,s,t,u } ).
Unlike an undirected graph where only a single vertex degree is defined, in a directed graph, every vertex has an out degree and an in degree. The out-degree is defined as total count of all outward drawn edges from that vertex. The in-degree is defined as the total count of all edges going towards a vertex. For instance, the out-degree of node A is one. While, the in-degree of node A is two. The Hand-shaking Lemma for directed graphs states that the sum of all in and out degrees for a graph is equal to two times the total number of edges. For example in Graph #2, the sum of all in and out degrees is equal to twelve(2*6 edges).
A Vertex that only has out bound edges with out any in bound edges is called a source. While, a vertex that only has in bound edges with out any out bound edges is called a sink. Graph #2 does not contain any sources. It does contain a single sink vertex C.
No comments:
Post a Comment