Unit-1
Introduction to Graph Theory
The analysis of lines and points is Graph Theory.
It is a mathematics sub-field that deals with graphs: diagrams that contain points and lines and that also represent mathematical truths in a pictorial way. The theory of graphs is the analysis of the interaction of edges and vertices. A graph is formally a pair (V, E), where a finite set of vertices is V and a finite set of edges is E.
|
Figure 1
1.1.1 Definitions
An arc is a line that is directed (a pair of ordered vertices).
The line connecting a pair of nodes is an edge.
The edges of an incident are edges that share a vertex. If the edge ties the vertex to another, an edge and a vertex exist.
An edge or arc that joins a vertex to itself is a loop.
A point or circle is a vertex, also called a node. It is the basic unit from which graphs are generated.
Vertices which are connected by an edge are adjacent vertices.
A vertex's degree is essentially the number of edges connected to the vertex. Twice the loops count.
The node (vertex) previous to a given vertex on a path is a predecessor.
The node (vertex) which follows a given vertex on a path is a successor.
A walk is a sequence of edges and vertices.
For every edge distinct, a circuit is a closed walk.
A closed walk is a walk back to itself from a vertex; a sequence of vertices and edges starting and ending at the same location.
A cycle is a closed walk without repeating vertices (except that the first and last vertices are the same).
A road is a walk where the vertices are not replicated. A route u-v is a path starting at u and terminating at v.
A walk with u-v will be a walk starting at u and stopping at v.
By combining the two vertices he used to merge, an edge contraction involves removing an edge from a graph.
A graph traversal in computer science and computer-based graph theory is an analysis of a graph in which one by one the vertices are visited or modified.
A Hamiltonian cycle is a loop that is closed where each node is visited precisely once.
1.2.1 Acyclic directed graph
A finite directed graph that has no driven cycles is an acyclic directed graph.
1.2.2 Directed graph
A directed graph is a graph where the edges have direction; that is, pairs of vertices are ordered.
|
Figure 2
1.2.3 Multigraph
The graph that occurs when you delete several edges is a condensation of a multigraph, leaving just one edge at any two points.
A multigraph is a loop-less graph, but which may have several edges.
|
Figure 3
A graph with no edges is a null graph. Maybe it has one or two vertices.
|
Figure 4
An oriented graph is a led graph with no symmetrical pairs of directed edges.
The graph is called a related graph if a graph has a path between each pair of vertices (there is no vertex not connected to an edge).
If, through repeated edge contractions or deletions, a graph G 'can be constructed from a graph G, the graph G' is a graph minor of G.
1.2.4 Inverted Graph
A graph with the same vertices but none of the same edges is an inverted graph G 'of G; two vertices in G' are adjacent if and only if in G they were not adjacent.
1.2.5 Plain graph
A plain graph is a graph with no loops or many edges at all. No multiple edges implies that the same endpoints are not visible on two edges.
1.2.6 Subgraph
A subgraph is a graph whose vertices and edges are part of another graph's vertices and edges (the supergraph).
1.2.7 Symmetric graph
A symmetric graph is a D-directed graph where the inverted arc (y,x) is also in D for each arc (x,y).
1.2.8 Trivial Graph
A graph with just a single vertex is a trivial graph.
1.2.9 Undirected graph
An undirected graph is a graph where no path is given to any of the edges; the pairs of vertices representing each edge are unordered.
1.2.10 Subgraphs
A Subgraph Q of a graph R is a graph whose vertex set V(Q) is a subset of the vertex set V(R), that is V(Q)⊆V(R), and whose edge set E(Q) is a subset of the edge set E(R), that is E(Q)⊆E(R).
|
Q (Subgraph of R) R
Let 'G-' be a simple graph with some vertices like 'G' and in 'G-' there is an edge {U, V}, if the edge is not present in G. This means that two vertices in 'G' are adjacent if the two vertices in G are not adjacent.
If in another graph II, the edges existing in graph I are absent, and if both graph I and graph II are combined to form a complete graph, then graph I and graph II are referred to as mutual complements.
|
Figure 4
Notice − A mixture of two additional graphs produces a complete graph.
If 'G' is any simple graph, then |E(G)| + |E('G-')| = |E(Kn)|, where n = number of vertices in the graph. |
Graph isomorphism is an equivalence relationship on graphs which, as such, splits the class into equivalence groups on all graphs. An isomorphism class of graphs is called a group of graphs isomorphic to one another. The two graphs shown below are isomorphic, despite their different looking drawings.
|
Figure 5
Two isomorphic plots A and B and one non-isomorphic plot C; Each of them has four vertices with three corners.
The degree of a vertex, in graph theory, is the number of edges connecting it. Vertex a has degree 5 in the following example, and the rest has degree 1. A degree 1 vertex is referred to as a "end vertex"
|
Figure 6
Euler path and Euler circuits
An Euler path is a path that uses any graph edge once precisely.
|
Figure 7
An Euler circuit is a circuit that uses each graph edge once precisely.
|
Figure 8
An Euler path begins and finishes at multiple vertices.
The circuit of An Euler begins and ends at the same vertex.
References
1. D.S. Chandrasekharaiah: Graph Theory and Combinatorics, Prism,2005.
2. Chartrand Zhang: Introduction to Graph Theory, TMH, 2006.
3. Richard A. Brualdi: Introductory Combinatorics, 4th Edition, Pearson Education, 2004.
4. Geir Agnarsson & Raymond Geenlaw: Graph Theory, Pearson Education, 2007.
