Types of Graph

Download
Share  Add to  Flag Embed
Views:
 
Category: Science & Tech..
     
 
License:   All Rights Reserved

Presentation Description

No description available.

Comments

 

By: mpsprashant (8 month(s) ago)

plz send me this presentation on my email:-mpsprashant@gmail.com

 

By: mpsprashant (8 month(s) ago)

plz send me this presentation on my email:-mpsprashant@gmail.com

 

By: mpsprashant (8 month(s) ago)

u have done very nice job for discrete maths student

Presentation Transcript

Introduction & Types Of Graphs:

Introduction & Types Of Graphs By : Preeti Mehta & Aakanksha Bhatnagar MCA 1 st Semester

Topics To Be Covered:

Topics To Be Covered Introduction & Basic Terminologies of : Graphs Directed & Undirected Graphs Simple , Multi & Pseudo Graphs Degree Null Graphs Handshaking Theorem Complete Graphs Bipartite Graphs Sub - Graphs & Super – Graphs Isomorphic Graphs

Graph:

Graph Graphs are bunch of vertices (or nodes) represented by circles which are connected by edges, represented by line segments Mathematically , a Graph G = (V,E) , consists of V , a non – empty set of vertices & E , set of edges which connects the elements in V. A Vertex v ε V (Set of all the vertices) is a point or node that is a member of graph G , usually representing an Entity. An Edge e ε E (Set of all the edges) is a connecting line that either joins two distinct vertices or a vertex to itself in a graph.

Slide 4:

Directed & Un – Directed Graphs A Directed Graph G consists of a set V of vertices & a set E of edges such that each edge e ε E is associated with an ordered pair of vertices . An Undirected Graph G consists of a set V of vertices & a set E of edges such that each edge e ε E is associated with an un-ordered pair of vertices .

Slide 5:

A Simple Graph is a graph in which each connects two distinct vertices & no two edges connects the same pair of vertices . A Simple Graph neither has a self – loop nor multiple edges . 1 2 3 4 {1,2} {3,4} {2,4} {1,3} {2,3} {1,4} Simple Graph

Slide 6:

A graph with parallel edges but no self – loops is known as multi – graph . e 1  {1,2}, e 2  {1,2}, e 3  {1,3}, e 4  {2,3}, e 5  {2,3}, e 6  {1,2} e 1 , e 2 & e 4 , e 5 are the multiple edges . 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6 Multi Graph

Slide 7:

If self – loops along with multiple edges are allowed , then we get a pseudo graph . e 1  {1,2}, e 2  {1,2}, e 3  {1,3}, e 4  {2,3}, e 5  {2}, e 6  {2}, e 7  {4} 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6 e 7 Pseudo Graph

Slide 8:

Vertices are adjacent if they are the endpoints of the same edge. Q: Which vertices are adjacent to 1? How about adjacent to 2, 3, and 4? 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6 Undirected Graph Terminology

Slide 9:

1 is adjacent to 2 and 3 2 is adjacent to 1 and 3 3 is adjacent to 1 and 2 4 is not adjacent to any vertex 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6

Slide 10:

Let u & v ε V , then the edge e that joins these two vertices is said to be incident on these two vertices. 1 2 3 4 e 1 e 2 e 3 e 4 e 5 e 6 Q: Which edges are incident to the vertices 1, 2, 3, and 4? Undirected Graph Terminology

Slide 11:

A: e 1 , e 2 , e 3 , e 6 are incident with 2 2 is incident with e 1 , e 2 , e 4 , e 5 , e 6 3 is incident with e 3 , e 4 , e 5 4 is not incident with any edge

Slide 12:

Degree of a vertex is the number of edges that are connected to that vertex . The degree ( deg G (v) ) of a vertex in an un-directed graph is the number of edges connected with it , a loop contributes twice to the degree of the vertex . In a directed graph , there are two types of degrees of a vertex : In – degree ( Indeg G (v) ) is the number of edges that ends at a vertex v ε V . Out – degree ( Outdeg G (v) ) is the number of edges that begins at a vertex v ε V . Degree

Slide 13:

The degree of a vertex in an un-directed graph is the number of edges that seem to be sticking to that edge of which the degree is to be found: 1 2 3 e 1 e 3 e 2 e 4 e 5 e 6 Degree

Slide 14:

1 2 3 e 1 e 3 e 2 e 4 e 5 e 6 magnify

Slide 15:

Thus deg(2) = 7 deg(2) = 1 + 1 + 1 + 2 + 2 = 7 1 2 3 e 1 e 3 e 2 e 4 e 5 e 6 magnify

Slide 16:

(Indeg)deg - (1) = 0 (Indeg)deg - (2) = 3 (Indeg)deg - (3) = 4 (outdeg)deg + (1) = 2 (outdeg)deg + (2) = 3 (outdeg)deg + (3) = 2 In a directed graph : 1 2 3 Degrees In Directed Graph

Slide 17:

A Graph which contains only isolated nodes is called a null graph , or in other words the set of edges in an isolated graph is empty . No Connecting edges Null Graph

Slide 18:

There are two ways to count the number of edges in the above graph: Just count the set of edges: 7 Count degrees of each vertex ,sum them all & divide by 2 . ( deg(1)+deg(2)+deg(3)+deg(4) )/2 = (3+7+2+2)/2 = 14/2 = 7 1 2 3 4 e 1 e 3 e 2 e 4 e 5 e 6 e 7 Handshaking Theorem

Slide 19:

In an undirected graph Q : In a party of 5 people can each person be friends with exactly three others? Handshaking Theorem

Slide 20:

A: Imagine a simple graph with 5 people as vertices and edges being undirected edges between friends Number of friends each person has is the degree of the person. Handshaking would imply that | E | = (sum of degrees)/2 or 2| E | = (sum of degrees) = (5x3) = 15. Impossible as 15 is not even. In general: The number of vertices of odd degree must be even in an undirected graph.

Slide 21:

A simple graph G is said to be complete if every vertex in G is connected with every other vertex , i.e. , if G contains exactly one edge between each pair of distinct vertices , a complete graph is denoted by the symbol K n where n denotes the number of vertices present in graph. Complete Graph

Slide 22:

A graph is Bipartite if the vertex set V can be partitioned into two subsets V 1 & V 2 (different) such that every edge in E connects a vertex in V 1 & vertex V 2 (so that no edge in G connects either two vertices in V 1 or two vertices in V 2 ). Bipartite graph of G can be denoted by (V 1 , V 2 ). Bipartite graph can have no loop. Bi – Partite Graph

Slide 23:

x 1 x 2 y 2 x 3 y 1 y 3 x 4 x 1 x 2 x 3 x 4 y 1 y 2 y 3 V 1 ={x 1 ,x 2 ,x 3 ,x 4 } V 2 ={y 1 ,y 2 ,y 3 } The above graph can be re – drawn as

Slide 24:

If G & H are graphs with vertex sets V(G) & V(H) & edge sets E(H) & E(G) respectively , such that V(H) is a subset of V(G) & E(H) is a subset of E(G). Then H is called the sub – graph of G & G is called the super – graph of H . Each edge of H has the same end points in H as in G. Spanning sub graph is a sub graph with V(H) = V(G) , but , need not contain all the edges in G . Sub Graph

Slide 25:

G ( Super Graph ) H ( Sub Graph )

Slide 26:

A sub graph of G can be obtained by removing certain vertices & edges from G . Removal of an edge leaves its vertices in place , a removal of vertex removes any edges with that vertex as an end point. If from a graph G with vertex set V , we delete a subset U of V , then (G-U) is called the vertex deleted sub graph. If a subset F of E is deleted from G , then (G-F) denotes edge deleted sub graph. If G is a graph with vertex set V & U is a subset of V , then the sub graph G(U) of G whose vertex set is U & whose edge set comprises exactly edges of E which joins vertices in U is known as induced sub graph of G.

Slide 27:

a b c d e f a b c d e a b c d e f Sub Graph Spanning Sub graph

Slide 28:

Let G 1 = (V 1 , E 1 ) & G 2 = (V 2 , E 2 ) be two graphs . A function f = V 1 → V 2 is called isomorphism if F is one – to – one onto For all a,b ε V 1 , {a,b} ε E 1 iff {f(a) , f(b) } ε E 2 , when such a function exists G 1 & G 2 are called isomorphic graphs & is written as G 1 ≈ G 2 . Graph Isomorphism

Slide 29:

a b c d 1 2 3 4 V 1 ={a,b,c,d} V 2 ={1,2,3,4} Isomorphic Graphs

Slide 30:

Q: Why are the following non-isomorphic? u 1 u 2 u 3 u 6 u 4 u 5 u 7 u 8 v 1 v 2 v 3 v 6 v 4 v 5 v 7 v 8

Slide 31:

For two graphs to be isomorphic graphs they should have the following properties : Same number of vertices , Same number of edges , Same degree sequences .

Slide 32:

A graph is a pictorial Representation of relation involving various entities. Traversal in an undirected graph is bidirectional between two vertices , while is not in the case of directional graphs where the traversal is only unidirectional. It is the edge in graph G that takes the credit of making two distinct vertices adjacent & being incident onto vertices that it joins. These properties form the very essence of Graph Theory. Degree of a vertex is the number of edges connected to it . Review Of Seminar