Graph Theory

Question 1

Graph Theory

Answer 1

Study of diagrams - networks, graphs

Question 2

Vertices/nodes

Answer 2

Points on the graph

Question 3

Edges/arcs

Answer 3

Lines that join vertices

Question 4

Faces/regions

Answer 4

Area enclosed by edges

Question 5

Loop

Answer 5

An edge that starts and ends at the same vertex

Question 6

Multiple Edges

Answer 6

Two or more edges connecting the same two vertices`

Question 7

Adjacent Vertices

Answer 7

Vertices that are connected by an edge

Question 8

Weighted Graph/Networks

Answer 8

Graphs that have amounts/distances on each edge

Question 9

Digraphs

Answer 9

Graphs that have directed edges/arcs

Question 10

Undirected Graphs

Answer 10

Graphs with no directed edges

Question 11

Simple Graph

Answer 11

An undirected graph with no loops and no multiple edges

Question 12

Simple Weighted Graphs

Answer 12

An undirected graph with no loops and no multiple edges

Question 13

Walk

Answer 13

A sequence of vertices for which each vertex in the sequence is joined to the next vertex by an edge - Can include repeat edges and vertices

Question 14

Closed Walk

Answer 14

A walk that finishes at the same vertex

Question 15

Open Walk

Answer 15

A walk that starts and finishes at different vertices

Question 16

Path

Answer 16

A walk that involves no repeat use of edges and no repeat use of vertices

Question 17

Open Path

Answer 17

A path that starts and finishes at different vertices

Question 18

Closed Path - Cycle

Answer 18

A path that starts and finishes at the same vertex

Question 19

Length

Answer 19

The number of edges the walk, path or cycle uses

Question 20

Trail

Answer 20

A walk having no repeated edges (can revisit vertices)

Question 21

Closed Trail

Answer 21

A trail that starts and finishes at the same vertex

Question 22

Connected Vertices

Answer 22

When a path exists from one vertex to another

Question 23

Adjacent Vertices

Answer 23

Two vertices connected by a path with only one edge

Question 24

Connected Graph

Answer 24

When every vertex is connected to at least one other vertex

Question 25

Bridge

Answer 25

Any edge in a connected graph which, when removed, leaves the graph disconnected

Question 26

Complete Graph

Answer 26

A simple graph in which every vertex is connected to every other vertex by a single edge

Question 27

Planar Graph

Answer 27

A graph that can be drawn in the plane, without its edges crossing over

Question 28

Eulers Rule

Answer 28

F + V = E + 2

Question 29

Subgraph

Answer 29

A selection of edges and vertices from a main graph

Question 30

Tree

Answer 30

Any connected simple graph that contains no cycles

Question 31

Bipartite

Answer 31

A graph in which the vertices can be divided into two disjoint sets such that each edge joins a vertex from one group to a vertex from the other group

Question 32

Degree or Order of a Vertex

Answer 32

The number of edges meeting at that vertex

Question 33

Odd Vertices

Answer 33

The order of a vertex is an odd number

Question 34

Even Vertices

Answer 34

The order of a vertex is an even number

Question 35

In-Degree

Answer 35

The number of edges coming into the vertex

Question 36

Out-Degree

Answer 36

The number of edges coming out of the vertex

Question 37

Traversable Networks

Answer 37

The network must be connected and have either zero or two odd vertices

Question 38

Eulerian Trail

Answer 38

A trail in a connected graph that travels every edge only once - Repeated vertices permitted

Question 39

Eulerian Circuit

Answer 39

A closed eulerian trail

Question 40

Semi Eulerian Trail

Answer 40

An open eulerian trail

Question 41

Hamiltonian Path

Answer 41

A path in a connected graph that visits every vertex in the graph only once

Question 42

Hamiltonian Cycle

Answer 42

A closed hamiltonian path

Question 43

Semi Hamiltonian

Answer 43

An open hamiltonian path