Basic Graph Theory Concepts
Königsberg bridge problem
Graph
theory may be said to have its beginning in 1736 when EULER considered
the (general case of the) Königsberg bridge problem:
Konigsberg is a city on the Pregel river in Prussia. The city occupied two islands plus on both banks.
Problem:-
Whether they could leave home, cross every bridge exactly once, and return home.
Konigsberg is a city on the Pregel river in Prussia. The city occupied two islands plus on both banks.
Problem:-
Whether they could leave home, cross every bridge exactly once, and return home.
A Graph
A graph G is consists of vertices and edges where V(G) is the set of
vertices and E(G) is the set of edges. Graphs in which there is no more
than one edge between any two vertices and in which no edge goes from vertex to
the same vertex are called simple graph. ie, a graph has no loops or multiple edges.
It is a simple graph
It is not simple
graph
Vertex: is the basic
element of graph. It drawn as a node or a dot.
Edge: is a set of two
elements. It drawn as a line connecting two vertices called end vertices, or
endpoints.
Loop, Multiple Edges
Loop: An edge whose end
points are equal.
Multiple edges: Edges
have the same pair of end points.
Adjacent, neighbors
Two vertices are adjacent and
are neighbors if they are the endpoints of an edge.
Here in this example A
and B are adjacent.
But A and D are not
adjacent.
Finite Graph, Null Graph
Finite graph Null graph
Finite graph: is a graph
whose vertex set and edge set are finite.
Null graph: the graph
whose vertex set and edges are empty.
Complement Graph
The complement G' of a
simple graph G is a simple graph where V(G')=V(G) and E(G')={uv| uv ÏE(G)}
Bipartite Graphs
A graph is bipartite if V(G) is the union of two
disjoint independent sets called partite sets of G. Also the vertices can be
partitioned into two sets such that each set is independent.
Path and Cycle
Path: a sequence of
distinct vertices such that two consecutive vertices are adjacent.
Eg: D,E,F,A,B,G,C is a path.
Cycle: is a closed Path.
Eg: E,F,A,B,C,D,E
Subgraphs
A subgraph of a graph G is a graph H such that V(H) Í V(G) and E(H) Í E(G) . The assignment of endpoints to edges in H is the same as in G.
G H
H is the sub graph of G.
Connected and Disconnected Graph
Connected graph is a graph in which there exists at least one path between two vertices.
The graphs which are not connected is called the disconnected graph.
Adjacency Matrix
Let G = (V, E), |V| = n and |E|=m
The adjacency matrix of G written A(G), is the n-by-n matrix in which entry ai,j
is the number
of edges in G with endpoints {vi,
vj}.
Isomorphism
An isomorphism
from a simple graph G to a simple
graph H is a bijection f : V(G)®V(H) such that uv ÎE(G) if and only if f(u)f(v) Î E(H).
We say “G is isomorphic to H”, written G
@ H
Complete Graph
Complete Graph is a simple graph whose vertices are pairwise adjacent.
Complete Bipartite Graph
Complete Bipartite Graph is a simple bipartite graph such that two vertices are adjacent if and only if they are in different partite sets.
Walk
A walk in a graph is a
sequence of vertices, each linked to the next vertex by a specified edge of the
graph.
Circuits
A circuit in a graph is a path
that begins and ends at the same vertex.
Planar Graphs
Cut-Edge, Cut Vertex
Hamilton Path and Cycle
A Hamiltonian cycle
Directed Graph
A directed graph or digraph G is a triple:
–A vertex set V(G),
–An edge set E(G), and
–A function assigning each edge an ordered pair of vertices.
•The first vertex of the ordered pair is the tail of the edge•The second is the head •Together, they are the endpoints.An edge is said to be from its tail to its head.
–The terms “head” and “tail” come from the arrows used to draw digraphs.
Star graph is a graph where exactly one vertex is connected to every other vertices, denoted by Sn.
–A vertex set V(G),
–An edge set E(G), and
–A function assigning each edge an ordered pair of vertices.
•The first vertex of the ordered pair is the tail of the edge•The second is the head •Together, they are the endpoints.An edge is said to be from its tail to its head.
–The terms “head” and “tail” come from the arrows used to draw digraphs.
Star Graph
Star graph is a graph where exactly one vertex is connected to every other vertices, denoted by Sn.
Wheel Graph
If a vertex is connected to every vertex of a cycle the resultant graph is called a wheel graph, denoted by Wn.
Path Graph
Path Graph is a continuous sequence of vertices & edges starting from a vertex & ending at another vertex, denoted by Pn.