Great Deal! Get Instant $10 FREE in Account on First Order + 10% Cashback on Every Order Order Now

For Exercises 3–9, determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops. Use your answers to determine the type of...

1 answer below »

For Exercises 3–9, determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops. Use your answers to determine the type of graph in Table 1 this graph is.

Table 1

TABLE 1 Graph Terminology.

Type

Edges

Multiple Edges Allowed?

Loops Allowed?

Simple graph

Undirected

No

No

Multigraph

Undirected

Yes

No

Pseudo graph

Undirected

Yes

Yes

Simple directed graph

Directed

No

No

Directed multigraph

Directed

Yes

Yes

Mixed graph

Directed and undirected

Yes

Yes

Answered Same Day Dec 29, 2021

Solution

David answered on Dec 29 2021
106 Votes
Graphs Eng.Jehad Aldahdooh
 Introduction To Graphs:

 Definitions:
 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 end points.
An edge is said to connect its endpoints.
 A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and a set
of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of
vertices. The directed edge associated with the ordered pair (u, v) is said to start at u
and end at v.

 Exercises

1. Determine whether the graph shown has directed or undirected edges, whether it has multiple
edges, and whether it has one or more loops. Use your answers to determine the type of graph
in Table 1 this graph is.
Solution:
Type Comment
3 Simple graph Undirected edges, no parallel edges or loops
4 multigraph Undirected edges, no loops but a parallel edges
5 Pseudograph Undirected edges, with loops and parallel edges
6 multigraph Undirected edges, no loops but a parallel edges
7 directed graph Directed edges, no parallel edges but loops.
8 directed multigraph Directed edges, parallel edges and loops.
9 directed multigraph Directed edges, parallel edges and loops.
 Graph Terminology
 Two vertices u and v in an undirected graph G are called adjacent (or neighbors) in G
if u and v are endpoints of an edge of G. If e is associated with {u, v}, the edge e is
called incident with the vertices u and v. The edge e is also said to connect u and v.
The vertices u and v are called endpoints of an edge associated with {u, v}.
 The degree of a vertex in an undirected graph is the number of edges incident with it,
except that a loop at a vertex contributes twice to the degree of that vertex. The degree
of the vertex v is denoted by deg (v).
o A vertex with degree 0 is called isolated.
o A vertex of degree 1 is called pendant.
 THE HANDSHAKING THEOREM Let G = (V, E) be an undirected graph with e
edges. Then
 When (u, v) is an edge of the graph G with...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here