Quiz about Graph Theory

Question 1

is the study of relationships, providing a helpful tool to quantify and simplify the moving parts of a dynamic system.

Accepted Answer

Graph Theory

Answer

Mathematical Modeling

Answer

Graph Modeling

Answer

Graph Relationship

Question 2

Graph theory was first introduced in the 18th century by the Swiss mathematician

Accepted Answer

Leonhard Euler

Answer

Leonhardt Euler

Answer

Leonhard Ruler

Answer

Leonhardt Ruler

Question 3

We think of a ______ as a set of points in a plane or in 3-space and a set of line segments (possibly curved), each of which either joins two points or joins a point to itself

Accepted Answer

Graph

Answer

Model

Answer

Line

Answer

Drawings

Question 4

is a mathematical structure consisting of two finite sets V and E.

Accepted Answer

Graph

Answer

Model

Answer

Line

Answer

Drawings

Question 5

The elements of V are called ______ (or nodes)

Accepted Answer

Vertices

Answer

Graph

Answer

Edge

Answer

Endpoints

Question 6

the elements of E are called ______

Accepted Answer

Edge

Answer

Graph

Answer

Vertices

Answer

Endpoints

Question 7

Each edge has a set of one or two vertices associated to it, which are called its _____

Accepted Answer

Endpoints

Answer

Graph

Answer

Vertices

Answer

Edge

Question 8

is said to join its endpoints

Accepted Answer

Edge

Answer

Graph

Answer

Vertices

Answer

Endpoints

Question 9

The ________ of a vertex v in a graph G, denoted N(v), is the set of all the neighbors of v.

Accepted Answer

Open Neighborhood

Answer

Closed Neighborhood

Question 10

is an edge that joins two distinct vertices.

Accepted Answer

proper edge

Answer

multi-edge

Answer

self-loop

Question 11

is an edge that joins a single endpoint to itself.

Accepted Answer

self-loop

Answer

proper edge

Answer

multi-edge

Question 12

is a collection of two or more edges having identical endpoints

Accepted Answer

multi-edge

Answer

proper edge

Answer

self-loop

Question 13

has neither self-loops nor multi-edges

Accepted Answer

simple graph

Answer

loopless graph

Answer

general graph

Question 14

may have multi-edges but no self-loops.

Accepted Answer

loopless graph

Answer

simple graph

Answer

general graph

Question 15

may have self-loops and/or multi-edges.

Accepted Answer

general graph

Answer

simple graph

Answer

loopless graph

Question 16

is an edge whose endpoints are equal.

Accepted Answer

loop

Answer

Multiple edges

Answer

simple graph

Answer

finite

Answer

adjacent and are neighbors

Question 17

are edges having the same pair of endpoints.

Accepted Answer

Multiple edges

Answer

loop

Answer

simple graph

Answer

finite

Answer

adjacent and are neighbors

Question 18

When u and v are the endpoints of an edge, they are

Accepted Answer

adjacent and are neighbors

Answer

loop

Answer

Multiple edges

Answer

simple graph

Answer

finite

Question 19

A graph is _____ if its vertex set and edge set are finite.

Accepted Answer

finite

Answer

loop

Answer

Multiple edges

Answer

simple graph

Answer

adjacent and are neighbors

Question 20

is a set of pairwise adjacent vertices

Accepted Answer

clique

Answer

complement

Answer

independent set

Question 21

is a set of pairwise nonadjacent vertices.

Accepted Answer

independent set

Answer

complement

Answer

clique

Question 22

is the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors.

Accepted Answer

chromatic number

Answer

bipartite

Answer

path

Answer

cycle

Question 23

A graph G is _______ if V(G) is the union of two disjoint (possibly empty) independent sets called partite sets of G

Accepted Answer

bipartite

Answer

chromatic number

Answer

path

Answer

cycle

Question 24

is a simple graph whose vertices can be ordered so that two vertices are adjacent if and only if they are consecutive in the list.

Accepted Answer

path

Answer

chromatic number

Answer

bipartite

Answer

cycle

Question 25

is a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent if and only if they appear consecutively along the circle.

Accepted Answer

cycle

Answer

chromatic number

Answer

bipartite

Answer

path

Question 26

written A(G), is the n-by-m matrix in which entry ai,j is the number of edges in G with endpoints {vi , vj}.

Accepted Answer

adjacency matrix

Answer

incidence matrix

Answer

incident

Answer

degree

Question 27

written M(G) is the n-by-m matrix in which entry mi,j is 1 if vi is an endpoint of ej and otherwise is 0

Accepted Answer

incidence matrix

Answer

adjacency matrix

Answer

incident

Answer

degree

Question 28

If vertex v is an endpoint of edge e, then v and e are

Accepted Answer

incident

Answer

adjacency matrix

Answer

incidence matrix

Answer

degree

Question 29

is a simple graph whose vertices are pairwise adjacent; the (unlabeled) ______ with n vertices is denoted Kn .

Accepted Answer

complete graph

Answer

complete bipartite graph

Answer

biclique

Question 30

is a simple bipartite graph such that two vertices are adjacent if and only if they are in different partite sets.

Accepted Answer

complete bipartite graph

Accepted Answer

biclique

Answer

complete graph

Question 31

is an edge,one of whose endpoints is designated as the tail, and whose other endpoint is designated as the head.

Accepted Answer

directed edge/arc

Answer

oppositely directed

Answer

multi-arc

Answer

directed graph

Answer

simple

Question 32

Two arcs between a pair of vertices are said to be _________ if they do not have the same head and tail.

Accepted Answer

oppositely directed

Answer

directed edge/arc

Answer

multi-arc

Answer

directed graph

Answer

simple

Question 33

s a set of two or more arcs having the same tail and same head

Accepted Answer

multi-arc

Answer

directed edge/arc

Answer

oppositely directed

Answer

directed graph

Answer

simple

Question 34

s a graph each of whose edges is directed.

Accepted Answer

directed graph

Answer

directed edge/arc

Answer

oppositely directed

Answer

multi-arc

Answer

simple

Question 35

A digraph is ______ if it has neither self-loops nor multi-arcs.

Accepted Answer

simple

Answer

directed edge/arc

Answer

oppositely directed

Answer

multi-arc

Answer

directed graph

Question 36

is a graph that has both undirected and directed edges

Accepted Answer

mixed graph

Answer

underlying graph

Question 37

is the graph that results from removing all the designations of head and tail from the directed edges of G.

Accepted Answer

underlying graph

Answer

mixed graph

Question 38

if v is not an endpoint of e

Accepted Answer

0

Answer

1

Answer

-1

Answer

2

Question 39

if v is the head of e

Accepted Answer

1

Answer

0

Answer

-1

Answer

2

Question 40

if v is the tail of e

Accepted Answer

-1

Answer

0

Answer

1

Answer

2

Question 41

if e is a self-loop at v

Accepted Answer

2

Answer

0

Answer

1

Answer

-1

Question 42

of a vertex v in a digraph is the number of arcs directed to v

Accepted Answer

Indegree

Answer

Outdegree

Question 43

of vertex v is the number of arcs directed from v

Accepted Answer

Outdegree

Answer

Indegree

Question 44

is a walk with no repeated edge.

Accepted Answer

trail

Answer

walk

Answer

length

Answer

endpoints

Question 45

A u, v-walk or u, v-trail has first vertex u and last vertex v; these are its ______

Accepted Answer

endpoints

Answer

walk

Answer

trail

Answer

length

Question 46

The ______ of a walk, trail, path, or cycle is its number of edges

Accepted Answer

length

Answer

walk

Answer

trail

Answer

endpoints

Question 47

The _________ of a subgraph G are its maximal connected subgraphs

Accepted Answer

Components

Answer

Trivial

Answer

Nontrivial

Answer

Isolated Vertex

Question 48

A component (or graph) is ______ if it has no edges;

Accepted Answer

Trivial

Answer

Components

Answer

Nontrivial

Answer

Isolated Vertex

Question 49

A component (or graph) is _______ if it has edges;

Accepted Answer

Nontrivial

Answer

Components

Answer

Trivial

Answer

Isolated Vertex

Question 50

is a vertex of degree 0.

Accepted Answer

Isolated Vertex

Answer

Components

Answer

Trivial

Answer

Nontrivial

Question 51

is an edge or vertex whose deletion increases the number of components.

Accepted Answer

cut-edge or cut-vertex

Answer

induced subgraph

Answer

bipartition

Question 52

obtained by deleting a set of vertices

Accepted Answer

induced subgraph

Answer

cut-edge or cut-vertex

Answer

bipartition

Question 53

A graph is ________ if it has a closed trail containing all edges

Accepted Answer

Eulerian

Answer

Circuit

Answer

Even Graph

Question 54

We call a closed trail a ______ when we do not specify the first vertex but keep the list in cyclic order

Accepted Answer

Circuit

Answer

Eulerian

Answer

Even Graph

Question 55

A graph G is _______ if and only if it has at most one nontrivial component and its vertices all have even degree.

Accepted Answer

Eulerian

Answer

Circuit

Answer

Even Graph

Question 56

Every _______ decomposes into cycles.

Accepted Answer

Even Graph

Answer

Eulerian

Answer

Circuit

Question 57

is a type of Depth First Search, where each node is visited in a certain order.

Accepted Answer

Pre-order Traversal

Answer

In-order Traversal

Answer

Post-order Traversal

Question 58

This traversal is mainly used for Binary Search Trees where it returns values in ascending order.

Accepted Answer

In-order Traversal

Answer

Pre-order Traversal

Answer

Post-order Traversal

Question 59

What makes this traversal is that visiting a node is done "after" the left and right child nodes are called recursively.

Accepted Answer

Post-order Traversal

Answer

Pre-order Traversal

Answer

In-order Traversal

Question 60

is a type of Binary Tree data structure, where the following properties must be true for any node "X" in the tree

Accepted Answer

Binary Search Tree

Answer

Binary Tree Spanning

Answer

Binary Tree Search

Answer

Binary Tree

Question 61

is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters.

Accepted Answer

Huffman Coding

Answer

Huffman Tree

Answer

Huffman Search Tree

Answer

Huffman Data Tree

Question 62

Given a tree (represented as graph, not as a rooted tree) with n labeled nodes with labels from 1 to n, a ______ uniquely identifies the tree. The sequence has n-2 values.

Accepted Answer

Prufer Code

Answer

Prufer Tree

Answer

Pruder Tree

Answer

Pruder Code

Question 63

is a recursive algorithm for searching all the vertices of a graph or tree data structure

Accepted Answer

Depth First Search Algorithm

Answer

Breadth First Search Algorithm

Answer

Pruder Code

Answer

Binary Search Tree

Question 64

starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

Accepted Answer

Breadth First Search Algorithm

Answer

Depth First Search Algorithm

Answer

Pruder Code

Answer

Binary Search Tree

Graph Theory

73 questions

is the study of relationships, providing a helpful tool to quantify and simplify the moving parts of a dynamic system.

Graph theory was first introduced in the 18th century by the Swiss mathematician

The city of K¨onigsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the _______

We think of a ______ as a set of points in a plane or in 3-space and a set of line segments (possibly curved), each of which either joins two points or joins a point to itself

is a mathematical structure consisting of two finite sets V and E.

The elements of V are called ______ (or nodes)

the elements of E are called ______

Each edge has a set of one or two vertices associated to it, which are called its _____

is said to join its endpoints

The ________ of a vertex v in a graph G, denoted N(v), is the set of all the neighbors of v.

Create a free account and access millions of resources

Similar Resources on Wayground

Popular Resources on Wayground

Discover more resources for Mathematics