Graph.pptx

n discrete mathematics, a graph is a collection of points, called vertices, and lines between those points, called edges. There are many different types of graphs, such as connected and disconnected graphs, bipartite graphs, weighted graphs, directed and undirected graphs, and simple graphs.

1. Graph : Discrete Mathematics Presentation Nasir Hussain Quaid- i -Azam University Islamabad. BS Computer Science 24

2. GRAPH Definition A graph G = (V ,E) consists of V , a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints. Computer Network Now suppose that a network is made up of data centers and communication links between computers. We can represent the location of each data center by a point and each communications link by a line segment.

3. Graph of Computer Network

4. Category of Graph On the base of definition there are two main category of graph: 1. Infinite Graph: A graph with an infinite vertex set or an infinite number of edges is called an infinite graph. 2. Finite Graph: A graph with a finite vertex set and a finite edge set is called a finite graph. Here we only consider finite graph.

5. Adjacent Vertex If two vertices are joined by the same edge, they are called adjacent vertex

6. Adjacent Edge If two edge are incident on same vertex they are called adjacent edge

7. Parallel edge When more than one edge associated with the same pair of vertices such edges are called parallel edges.

8. Types of Graph UN-DIRECTED GRAPH: A set of object that are connected together, where all the edges are bidirectional. Simple Graph Multi Graph Pseudo Graph DIRECTED GRAPH: Simple Directed Graph Directed Multigraph MIXED GRAPH.

9. SIMPLE GRAPH DEFINITION: A graph in which each edge connects two different vertices and where no two edges connect the same pair of vertices is called a simple graph.  .

10. no two edges connect the same pair of vertices

11. The maximum number of edge possible in a single graph with ‘n’ vertices is; n C 2 = n(n-1)/2

12. Exercise Question(pg # 650) Q(1-10) 10. For each undirected graph in Exercises 3–9 that is not simple, find a set of edges to remove to make it simple. Qno : 03 This graph is simple because each edge is connected with two different vertices.

13. Qno 6; Not a simple Graph. We can make it simple graph by removing only one edge between a and c and between b and d.

14. MULTI GRAPH Definition: Graphs that may have multiple edges connecting the same vertices are called multigraphs.

15. QNO : 4

16. Pseudo Graph Definition Graphs that may include loops, and possibly multiple edges connecting the same pair of vertices or a vertex to itself, are sometimes called pseudographs.

17. Multiple Edges Allowed? Loop Allowed? Simple Graph NO NO Multi Graph YES NO Pseudo Graph YES YES Graph Terminology