Discrete Mathematics - Graphs

Question 1

What is a Graph

Answer 1

A diagram of vertices connected by edges

Question 2

What is a vertex

Answer 2

A point on a graph where edges meet and intersect

Question 3

What is an edge

Answer 3

A line connected to a vertex

Question 4

What is an Isomorphic Graph

Answer 4

A graph that display the same set of veritces and edges as another graph

Question 5

What is a connected graph

Answer 5

A graph by which you can travel from one vertex to any other vertex on the graph

Question 6

What are multiple edges

Answer 6

Two or more egdes that connect to the same pair of vertices

Question 7

What is a loop

Answer 7

A vertex connected to itself by the same edge

Question 8

What is meant by the degree of a vertex

Answer 8

The number of edges that a vertex is incedent ( connected ) to

Question 9

What is a Simple graph

Answer 9

A graph that has no multiple edges or loops

Question 10

What is a Sub-graph

Answer 10

A graph formed by some of the vertices and edges of the original graph

Question 11

What is a Planar Graph

Answer 11

A graph that has no edges that cross over each other

Question 12

What is a Bipartite graph

Answer 12

A graph containing 2 distinct sets of vertices that have edges which connect vertices from one set to another

Question 13

How is a Bipartite Graph denoted

Answer 13

Kₙ,ₘ where ₙ is the number of vertices in the 1st set and, ₘ is the number of vertices in the 2nd set.

Question 14

What is a Complete Graph

Answer 14

A simple graph where each vertex is connected to all other vertices within the graph by an edge

Question 15

How is a Complete graph denoted

Answer 15

Kₙ where ₙ is the number of vertices in the graph.

Question 16

What is a subdivision

Answer 16

Where a vertex has been added to an edge, between a direct pair of vertices

Question 17

What is the equation relating the number of degrees and edges within a graph

Answer 17

Degrees (D) = 2 x Edges (E)

Question 18

What is a Euler’s Formula

Answer 18

V + F - E =2

Question 19

What is a face in a graph

Answer 19

Areas created by edges drawn on a plane

Question 20

What is an adjacency matrix

Answer 20

A table showing the vertices and the number of connections between them

Question 21

How is a Complement Graph denoted

Answer 21

G’

Question 22

What is a walk

Answer 22

A sequence of vertices and edges

Question 23

What is a trail

Answer 23

A walk with no repeated edges

Question 24

What is a Cycle

Answer 24

A Trail with no repeated vertices, that starts and finishes on the same vertex

Question 25

Explain why Kₙ,ₘ has mn edges

Answer 25

Each vertex in the first set is connected by an edge to each vertex in the other set. Meaning that there are n edges for every m vertices

Question 26

Where is an adjacency matrix symetrical from

Answer 26

The lead diagonal

Question 27

What is meant by the complement of a simple graph

Answer 27

A set of edges such that when added to the original graph gives a complete graph

Question 28

What is a tree

Answer 28

A simple-connected graph that has the minimum number of egdes

Question 29

What is the trend for the degrees of vertices in a tree / tree branch

Answer 29

The vertices at the end of the branch have a degree of 1. This means a tree with n vertices must have a minimum of 2 vertices with degree 1 and a maximum of n - 1 vertices of degree 1.

Question 30

What is a Traversable graph

Answer 30

A graph that can be drawn as a trail that visits every edge

Question 31

What is an Eulerian Graph

Answer 31

A graph that has no vertices with an odd degree

Question 32

What is a Semi-Eulerian Graph

Answer 32

A graph that has exactly 2 vertices with an odd degree

Question 33

What is a Hamiltonian Graph

Answer 33

A graph that contains a cycle that passes through each vertex once, and starts and ends on the same vertex