Scribd
Upload
7 views5 pages

Assignment 2 Graph

The document categorizes different types of graphs including simple graphs, multigraphs, and directed multigraphs based on their edges and loops. It discusses the isomorphism between two graphs G and H, demonstrating their equivalence through a one-to-one vertex correspondence. Additionally, it provides an adjacency matrix for graph G2 and details the vertices, directed edges, and their respective in-degrees and out-degrees for a directed multigraph.

Uploaded by

mifta ardianti
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views5 pages

Assignment 2 Graph

The document categorizes different types of graphs including simple graphs, multigraphs, and directed multigraphs based on their edges and loops. It discusses the isomorphism between two graphs G and H, demonstrating their equivalence through a one-to-one vertex correspondence. Additionally, it provides an adjacency matrix for graph G2 and details the vertices, directed edges, and their respective in-degrees and out-degrees for a directed multigraph.

Uploaded by

mifta ardianti
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Assignment:2 graph

Solutions
For no1: Single edges, Undirected edges , No loop = Simple graph
For no2: Multiple edges , undirected edges, No loops = Multigraph
For no3: Multiple edges , Directed edges, Loop present= Directed multigraph
For no4: Multiple edges , Directed edges, Loop present= Directed multigraph

5th: Determining Whether Graphs G and H Are Isomorphic

Graphs G and H each contain six vertices and share the same degree sequence.
Both graphs consist of a four-vertex cycle with two additional interior vertices connected in the
same pattern.
Since there exists a one-to-one correspondence between their vertices that preserves
adjacency, the two graphs are isomorphic.

There for
Hence both are iso morphic

6. Adjacency Matrix of Graph G2

Let the vertices be ordered as .


Based on the edges in the diagram, the adjacency relations are:

a is adjacent to b and d.

b is adjacent to a,d and e.

c is adjacent to d and e.

d is adjacent to a ,b and c.

e is adjacent to b and c .

The adjacency matrix is:


7. Vertices, Edges, In-Degree and Out-Degree of the Directed Multigraph

Number of vertices: 4

{a,b,c,d}

Directed edges (from the diagram):

1. a to a (loop)
2. a to b
3. b to c
4. d to a
5. d to a
6. d to c
7. c to d
Total number of directed edges: 7

In-Degree and Out-Degree of Each Vertex


Vertex a

In-degree: 2 (a to a )

Out-degree: 2 (a to a , a to b )

Vertex b

In-degree: 2 (a to b , d to b )

Out-degree: 1 (b to c)

Vertex c

In-degree: 2 ( b to c,b to a )

Out-degree: 1 ( c to d )

Vertex d

In-degree: 1 (c to d)

Out-degree: 3 (d to a ,d to b ,d to c )

You might also like