Basics Of Graph Theory

  • Uploaded by: purijatin
  • 0
  • 0
  • June 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Basics Of Graph Theory as PDF for free.

More details

  • Words: 1,356
  • Pages: 31
Graphs

Nitin Upadhyay February 24, 2006

Discussion 

What is a Graph?



Applications of Graphs



Categorization



Terminology

What is a Graph? A graph G=(V,E) consists of a finite nonempty set V, the elements of which are the vertices of G, and a finite set E of unordered pairs of distinct elements of V called edges. G = ( V, E ) Where, V - set of vertices E - set of edges

V = {1, 2, 3, 4, 5}

3

1 Edge

4

E = { (1,2), (1,3), (1,4), (2,3), (3,5), (4,5) }

Vertex (Node)

2 5

Graph applications 

Graphs can be used for:           

Finding a route to drive from one city to another Finding connecting flights from one city to another Determining least-cost highway connections Designing optimal connections on a computer chip Implementing automata Implementing compilers Doing garbage collection Representing family histories Doing similarity testing (e.g. for a dating service) Pert charts Playing games

Graph applications 

Computer

Computer Networks

Resistor/Inductor/…



Electrical Circuits



Road Map City

Graph Models      



Acquaintanceship Graphs – showing whether two people know each other, that is, whether they are acquainted. Influence Graphs – showing whether a person can influence another (e.g., a  b) by using a directed graph. The Bollywood Graph – showing whether the actors have worked together in a movie. Round-Robin Tournaments – showing if team a beats team b (using an edge (a, b)) via a directed graph. Collaboration Graphs – modeling joint authorship of academic papers (an edge links two people if they have jointly written a paper). Call Graphs – modeling telephone calls made in a network (can use either directed multigraphs or undirected ones, depending on the interest) The Web Graph – representing hyperlinks between Web pages using a directed graph. E.g., Web page a links to Web page b via an edge pointing from a to b.

Structure of the Internet SOURCE: CISCO SYSTEMS NAP

Europe

Backbone 1 NAP

Backbone 4, 5, N

Japan Regional A

Backbone 2

NAP

NAP

Backbone 3

Australia

Regional B

MAPS

UUNET MAP

Graph Models 

Where are we right now?

Graph categorization      

Simple Graphs Multigraphs Pseudographs Directed Graphs Directed Multigraphs Weighted Graph

Simple Graphs 

A simple graph G = (V,E) consists of: 



a set V of vertices or nodes (V corresponds to the universe of the relation R), a set E of edges / arcs / links: unordered pairs of distinct elements u, v ∈ V, such that uRv.

Multigraphs 





Like simple graphs, but there may be more than one edge connecting two given nodes. A multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges (as primitive objects), and a function f from E to Parallel edges {{u,v}| u,v∈V ∧ u≠v}. The edges e1 and e2 are called multiple or parallel edges if f(e1) = f(e2).



E.g., nodes are cities, edges are segments of major highways

Pseudographs 





Like a multigraph, but edges connecting a node to itself are allowed. A pseudograph G=(V, E, f ) where f:E→{{u,v}|u,v∈V}. Edge e∈E is Self loops a loop if f(e)={u,u}={u}. E.g., nodes are campsites in a state park, edges are hiking trails through the woods.

Directed Graphs 





Correspond to arbitrary binary relations R, which need not be symmetric. A directed graph (V,E) consists of a set of vertices V and a binary relation E on V. E.g.: V = people, E={(x,y) | x loves y}

Directed Multigraphs 





Like directed graphs, but there may be more than one arc from a node to another. A directed multigraph G=(V, E, f ) consists of a set V of vertices, a set E of edges, and a function f:E→V×V. E.g., V=web pages, E=hyperlinks. The WWW is a directed multigraph...

Weighted Graph 

A Weighted Graph is a graph where all the edges are assigned weights 50

1 20

3 30

40 2

40

4 30

5

Graph Terminology 

Adjacent, connects, endpoints, degree, initial, terminal, in-degree, out-degree, complete, cycles, wheels, n-cubes, bipartite, subgraph, union.

Adjacency Let G be an undirected graph with vertices u and v, and a linking edge e = {u,v}. Then we say:  u, v are adjacent / neighbors / connected.  Edge e is incident with vertices u and v.  Edge e connects u and v.  Vertices u and v are endpoints of edge e.

Adjacency 



Adjacent vertices: If (i,j) is an edge of the graph, then the nodes i and j are adjacent An edge (i,j) is Incident to vertices i and j 3

1

Vertices 2 and 5 are not adjacent

2 4 5

Degree of a Vertex  

 

Let G be an undirected graph with vertex v. The degree of v, deg(v), is its number of incident edges. (Except that any self-loops are counted twice.) A vertex with degree 0 is isolated. A vertex of degree 1 is pendant.

A Degree Example 

What are the degrees of the vertices in the graphs G and H as shown below? In G, deg(a) = 2, deg(b) = deg(c) = deg(f) = 4, deg(d) = 1, deg(e) = 3 and deg(g) = 0 In H, deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1, deg(d) = 5

a

b

c

d

a

f

e

g

e

c

b

d

Handshaking Theorem 

Let G = (V, E) be an undirected (simple, multi-, or pseudo-) graph with e edges. Then



Corollary: Any undirected graph has an even number of vertices of odd degree.

Handshaking Theorem Example 

How many edges are there in a graph with ten vertices each of degree six? The sum of the degrees of the vertices is 6x10 = 60, it follows that 2e = 60. Therefore, e = 30.

Directed Adjacency 

Let G be a directed (possibly multi-) graph, and let e be an edge of G that is (or maps to) (u,v). Then we say:     

u is adjacent to v, v is adjacent from u e comes from u, e goes to v. e connects u to v, e goes from u to v the initial vertex of e is u the terminal vertex of e is v

Directed Degree 

Let G be a directed graph, v a vertex of G. 





The in-degree of v, deg−(v), is the number of edges going to v. The out-degree of v, deg+(v), is the number of edges coming from v. The degree of v, deg(v)≡deg−(v)+deg+(v), is the sum of v’s in-degree and out-degree.

Directed Handshaking Theorem 

Let G = (V, E) be a directed (possibly multi-) graph with vertex set V and edge set E . Then:



Note that the degree of a node is unchanged by whether we consider its edges to be directed or undirected.

Path  



Path: A sequence of edges in the graph There can be more than one path between two vertices Vertex A is reachable from B if there is a path from A to B G A

Paths from B to D - B, A, D - B, C, D -

F

D B C

E

Path 

Simple Path: A path where all the vertices are distinct 3

1 2 4 5

1,4,5,3 is a simple path. But 1,4,5,4 is not a simple path.

Length 

Length : Sum of the lengths of the edges on the path. 3

1

Length of the path 1,4,5,3 is 3

2 4 5

Circuit 

Circuit: A path whose first and last vertices are the same 3

1

The path 3,2,1,4,5,3 is a circuit.

2 4 5

Cycle 

Cycle: A circuit where all the vertices are distinct except for the first (and the last) vertex 3

1

1,4,5,3,1 is a cycle

2

1,4,5,4,1 is not a cycle

4 5

Questions Questions ?

Related Documents

Basics Of Graph Theory
June 2020 11
Graph Theory
June 2020 3
Graph Theory
November 2019 7
Graph Theory Mid Sem.pdf
October 2019 9
Intro To Graph Theory
June 2020 6

More Documents from ""

Chapter 5
June 2020 10
Graphs Lect3
June 2020 8
Pspice Final
May 2020 4
Algorithm Making
May 2020 9