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.

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

                A graph (or multigraph) G is called planar. If G can be drawn in the plane with its edges intersecting only at vertices of G. Such a drawing of G is called an embedding of G in the plane.

Cut-Edge, Cut Vertex

                   Cut-edge or cut-vertex of a graph is an edge or vertex whose deletion increases the number of components.

Hamilton Path and Cycle

              A Hamiltonian cycle  

                      A Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamilton cycle is a Hamiltonian path that is a cycle.

                         Determining whether such paths and cycles exists in graph is the Hamiltonian path problem.

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

             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.

Multigraph

                     If in any graph between two vertices there exists more than one relation they are connected by more than one edge. Such edges are called parallel edges or multiple edges.

                  If in any graph there exists at least one pair of parallel edges such a graph is called multigraph.