Graphs: Nitin Upadhyay

  • 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 Graphs: Nitin Upadhyay as PDF for free.

More details

  • Words: 1,483
  • Pages: 29
Graphs

Nitin Upadhyay February 25, 2006

Discussion 

What is a Graph?



Applications of Graphs



Categorization



Terminology

Discussion 

Hamiltonian Cycle



Special Graph Structures



Graph Representations

Hamiltonian Cycle 

Hamiltonian Cycle: A Cycle that contains all the vertices of the graph 3

1

1,4,5,3,2,1 is a Hamiltonian Cycle

2 4 5

Special Graph Structures Special cases of undirected graph structures:  Complete graphs K n 

Cycles Cn



Wheels Wn



n-Cubes Qn



Bipartite graphs Complete bipartite graphs Km,n



Revisiting Paths and cycles 

A path is a sequence of nodes v1, v2, …, vN such that (vi,vi+1)∈E for 0


The length of the path is N-1. Simple path: all vi are distinct, 0
A cycle is a path such that v1=vN 

An acyclic graph has no cycles

Complete Graphs 

For any n∈N, a complete graph on n vertices, Kn, is a simple graph with n nodes in which every node is adjacent to every other node: ∀ u,v∈V: u≠v↔{u,v}∈E.

K1

K4 K3 K2 n(n − 1) Note that Kn has ∑i = 2 edges. n −1 i =1

K5

K6

Cycles 

For any n≥3, a cycle on n vertices, Cn, is a simple graph where V={v1,v2,… ,vn} and E={{v1,v2},{v2,v3},…,{vn−1,vn},{vn,v1}}.

C3

C4

C5

C6

C7

How many edges are there in Cn?

C8

Wheels 

For any n≥3, a wheel Wn, is a simple graph obtained by taking the cycle Cn and adding one extra vertex vhub and n extra edges {{vhub,v1}, {vhub,v2},…,{vhub,vn}}. W3

W4

W5

W6

W7

How many edges are there in Wn?

W8

n-cubes (hypercubes) 

For any n∈N, the hypercube Qn is a simple graph consisting of two copies of Qn-1 connected together at corresponding nodes. Q0 has 1 node. Q0

Q1

Q2

Q3

Q4

Number of vertices: 2n. Number of edges:Exercise to try!

Bipartite Graphs 





Let G=(V,E) be a graph, G is said to be bipartite graph: If its vertex set V can be partitioned into two nonempty disjoint subsets V1 and V2, called a bipartition. And edge connecting one of its end in V1 and other with V2.

Complete Bipartite Graphs 



A complete bipartite graph is a bipartite graph with partition V1 and V2 in which each vertex of V1 is joined by an edge to each vertex of V2. A complete bipartite graph with | V1 | = m and | V2 | = n is denoted as Km,n.

Subgraphs 

A subgraph of a graph G=(V, E) is a graph H=(W, F) where W⊆V and F⊆E.

G

H

Graph Representations     

Adjacency-matrix representation Incidence Matrix representation Edge-set representation Adjacency-set representation Adjacency List

Adjacency-matrix Adjacency Matrix Representation representation A

C



E

D G A B C D E F G

B

F

AB CD EF G





One simple way of representing a graph is the adjacency matrix A 2-D array has a mark at [i][j] if there is an edge from node i to node j The adjacency matrix is symmetric about the main diagonal

Adjacency-matrix representation 

Adjacency Matrix (A) 



The Adjacency Matrix A=(ai,j) of a graph G=(V,E) with n nodes is an nXn matrix Each element of A is either 0 or 1, depending on the adjacency of the nodes.

aij =

1

if (i,j) Є E

0

otherwise

Adjacency-matrix representation 

Find the adjacency matrices of the following 1 2 3 4 5 graphs 3

1 2 4

5 3

1 2

1 0 2 1 3 1

1

1

1

0

0

1

0

0

1

0

0

1

4 1

0

0

0

1

5 0

0

1

1

0

1

2

3

1 0 2 0

1

0

0

1

3 1

1

0

Adjacency-matrix Representation representation  A

C

E

D G A B C D E F G

B

F

AB CD EF G



An adjacency matrix can equally well be used for digraphs (directed graphs) A 2-D array has a mark at [i][j] if there is an edge from node i to node j

Incidence Matrices 

Let G = (V, E) be an undirected graph and v1, v2, …, vn be the vertices and e1, e2, …, em be the edges of G. Then the incidence matrix with respect to this ordering of V and E is the n x m matrix M = [mij], where 1

when edge ej is incident with vi,

0

otherwise

mij =

Incidence Matrix Example Represent the graph shown below with an incidence matrix. v1

e1

v2

v3

e3

v4

e9

v5

e8

e5

e4

e7

e6

e2



v6

e1 v 1 1 v 2 1  v3  0  v4  x v5  x  v6  x

For your exercise

e2 1 0 0 x x x

e3 0 1 1 x x x

e4 0 1 0 x x x

e5 0 1 0 x x x

e6 0 1 0 x x x

e7 0 0 1 x x x

e8 0 0 1 x x x

e9 0 0  0  x x  x 

Edge-set representation 









An edge-set representation uses a set of nodes and a set of edges  The sets might be represented by, say, linked lists  The set links are stored in the nodes and edges themselves The only other information in a node is its element (that is, its value)—it does not hold information about its edges The only other information in an edge is its source and destination (and attribute, if any)  If the graph is undirected, we keep links to both nodes, but don’t distinguish between source and destination This representation makes it easy to find nodes from an edge, but you must search to find an edge from a node This is seldom a good representation

Edge-set representation 

A

s 



nodeSet = {A, B, C, D, E, F, G}

edge t D w

p E

G

u

B

r

q

C

edgeSet = { p: (A, E), q: (B, C), r: (E, B),

v F

Here we have a set of nodes, and each node contains only its element (not shown)

s: (D, D), t: (D, A), u: (E, G), v: (F, E), w: (G, D) }

Each edge contains references to its source and its destination (and its attribute, if any)

Adjacency-set representation 

An adjacency-set representation uses a set of nodes 





Each node contains a reference to the set of its edges For a directed graph, a node might only know about (have references to) its out-edges

Thus, there is not one single edge set, but rather a separate edge set for each node 

Each edge would contain its attribute (if any) and its destination (and possibly its source)

Adjacency-set representation A 

Adjacency A

s 



t D w

p E

G

u

B

r

q

C

v F

Here we have a set of nodes, and each node refers to a set of edges

{p}

p: (A, E)

B

{q}

q: (B, C)

C

{}

r: (E, B)

D

{ s, t }

s: (D, D)

E

{ r, u }

t: (D, A)

F

{v}

u: (E, G)

G

{w}

v: (F, E)

Each edge contains references to its source and its destination (and its attribute, if any)

w: (G, D)

Adjacency-set representation 

If the edges have no associated attribute, there is no need for a separate Edge class  





Instead, each node can refer to a set of its neighbors In this representation, the edges would be implicit in the connections between nodes, not a separate data structure

For an undirected graph, the node would have references to all the nodes adjacent to it For a directed graph, the node might have:  

references to all the nodes adjacent to it, or references to only those adjacent nodes connected by an out-edge from this node

Adjacency-set representation 

A

{E}

B

{C}

C

{}

D

{ D, A }

F

E

{ B, G }

Here we have a set of nodes, and each node refers to a set of other (pointed to) nodes The edges are implicit

F

{E}

G

{D}

Adjacency A

G



C

E

D



B

Adjacency List 

An Adjacency list is an array of lists, each list showing the vertices a given vertex is adjacent to 3

1 2 4 5

1

2

2

1

3

3

1

5

4

1

5

5

Adjacency List 

Adjacency List of a Weighted Graph 

The weight is included in the list

9

1 4

2

3 5

1

2 4

2

3 5

3

1 9

2 5

Questions Questions ?

Related Documents

Nitin
November 2019 19
Graphs
June 2020 18
Graphs
November 2019 37
Graphs
May 2020 36

More Documents from "Maribel Sarabia Juste"

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