ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Graph theory 1

?Download as PPTX, PDF?
?
RidaZaman1
RidaZaman1

A graph is a collection of vertices and edges that connect them. It is represented visually as dots (vertices) connected by lines (edges). Formally, a graph is defined as a non-empty finite set of vertices V along with a set E of 2-element subsets of V, where the elements of V are called vertices and the elements of E are called edges. Properties of graphs include the degree of vertices, which indicates the number of edges connected to that vertex, and whether a graph is directed or undirected based on whether the edges have a designated direction or not. Graphs can model real-world networks like roads between cities or relationships between people.

1 of 20
Download to read offline
MADE BY RIDA ZAMAN 1
? In simple words graph is a collection of vertices and edges. ? All the graph is lines & dots connecting to each other. ? A graph is a non empty finite set of vertices V along with a set of E of 2-elements subset of V. ? The elements of V are called Vertices(NODES) the elements of E are called Edges. MADE BY RIDA ZAMAN 2
V1 V2 V3 V4 V6 V5 V={V1,V2,V3,V4,V5,V6} TOTAL NUMBER OF VERTICES TOTAL NUMBER OF EDGES E={{V1,V2}{V1,V3}{V1,V4} {V4,V5}{V5,V6}} MADE BY RIDA ZAMAN 3
V1 V2 V3 V4 V6 V5 Cardinality of graph represents number of vertices |G|=(absolute value) |G|=6 MADE BY RIDA ZAMAN 4
? It tells number of edges coming out of a vertex. Degree of V1 Deg(V1)=3 MADE BY RIDA ZAMAN 5
? There can be degree zero of any vertex. MADE BY RIDA ZAMAN V1 V2 V3 V4 Degree of V1 Deg(V1)=0 6
? It doesn¡¯t matter how we connect one point to another in a graph, ? unless all the original information is same and original connection ,and nothing is missing MADE BY RIDA ZAMAN 7
SHOWS WHAT VERTEX IS ADJACENT TO OTHER MADE BY RIDA ZAMAN 5 8
IT SHOWS THE CONNECTIVITY BETWEEN VERTEX THROUGH MATRIX MADE BY RIDA ZAMAN 9
? A loop is an edge that connects a vertex to itself. ? A simple graph contains no loops. Deg(V1)=4 V1 V2 V3 MADE BY RIDA ZAMAN 10
? Multi edges are two or more edges that are incident to the same two vertices. Deg(V1)=3 MADE BY RIDA ZAMAN 11
? Are those graph where vertex have loop back on them regular graph don¡¯t have loops. MADE BY RIDA ZAMAN 12
? A path is sequence of distinct edges you can follow through graph ? The number of edges is called length of path ? You cant repeat the edges when you are supposed to find any path ? If we have two graphs and you can find a path between them then the graph is said to be connected other wise disconnected MADE BY RIDA ZAMAN 13
MADE BY RIDA ZAMAN 14 10 15 10 3 3 15 10 5 5 10
? In directed edges there is an arrow on an edge which indicates where it goes, it tells the starting & end point of an edges. E= {{v1,v2}} MADE BY RIDA ZAMAN 15
MADE BY RIDA ZAMAN 16
? In undirected edges there is no direction. E= {{v1,v2}{v2,v1}} MADE BY RIDA ZAMAN 17
MADE BY RIDA ZAMAN 18 V2
? We use graph for solving network related problems ? Graph represent set of similar things and the connection between them e.g: Cities and the roads connecting them Networks of friendship among people Website and their links to other sites MADE BY RIDA ZAMAN 19
MADE BY RIDA ZAMAN 20

More Related Content

Graph theory 1

  • 1. MADE BY RIDA ZAMAN 1
  • 2. ? In simple words graph is a collection of vertices and edges. ? All the graph is lines & dots connecting to each other. ? A graph is a non empty finite set of vertices V along with a set of E of 2-elements subset of V. ? The elements of V are called Vertices(NODES) the elements of E are called Edges. MADE BY RIDA ZAMAN 2
  • 3. V1 V2 V3 V4 V6 V5 V={V1,V2,V3,V4,V5,V6} TOTAL NUMBER OF VERTICES TOTAL NUMBER OF EDGES E={{V1,V2}{V1,V3}{V1,V4} {V4,V5}{V5,V6}} MADE BY RIDA ZAMAN 3
  • 4. V1 V2 V3 V4 V6 V5 Cardinality of graph represents number of vertices |G|=(absolute value) |G|=6 MADE BY RIDA ZAMAN 4
  • 5. ? It tells number of edges coming out of a vertex. Degree of V1 Deg(V1)=3 MADE BY RIDA ZAMAN 5
  • 6. ? There can be degree zero of any vertex. MADE BY RIDA ZAMAN V1 V2 V3 V4 Degree of V1 Deg(V1)=0 6
  • 7. ? It doesn¡¯t matter how we connect one point to another in a graph, ? unless all the original information is same and original connection ,and nothing is missing MADE BY RIDA ZAMAN 7
  • 8. SHOWS WHAT VERTEX IS ADJACENT TO OTHER MADE BY RIDA ZAMAN 5 8
  • 9. IT SHOWS THE CONNECTIVITY BETWEEN VERTEX THROUGH MATRIX MADE BY RIDA ZAMAN 9
  • 10. ? A loop is an edge that connects a vertex to itself. ? A simple graph contains no loops. Deg(V1)=4 V1 V2 V3 MADE BY RIDA ZAMAN 10
  • 11. ? Multi edges are two or more edges that are incident to the same two vertices. Deg(V1)=3 MADE BY RIDA ZAMAN 11
  • 12. ? Are those graph where vertex have loop back on them regular graph don¡¯t have loops. MADE BY RIDA ZAMAN 12
  • 13. ? A path is sequence of distinct edges you can follow through graph ? The number of edges is called length of path ? You cant repeat the edges when you are supposed to find any path ? If we have two graphs and you can find a path between them then the graph is said to be connected other wise disconnected MADE BY RIDA ZAMAN 13
  • 14. MADE BY RIDA ZAMAN 14 10 15 10 3 3 15 10 5 5 10
  • 15. ? In directed edges there is an arrow on an edge which indicates where it goes, it tells the starting & end point of an edges. E= {{v1,v2}} MADE BY RIDA ZAMAN 15
  • 16. MADE BY RIDA ZAMAN 16
  • 17. ? In undirected edges there is no direction. E= {{v1,v2}{v2,v1}} MADE BY RIDA ZAMAN 17
  • 18. MADE BY RIDA ZAMAN 18 V2
  • 19. ? We use graph for solving network related problems ? Graph represent set of similar things and the connection between them e.g: Cities and the roads connecting them Networks of friendship among people Website and their links to other sites MADE BY RIDA ZAMAN 19
  • 20. MADE BY RIDA ZAMAN 20