Decision - graph theory terms

Question 1

Vertex (verticies) / node

Answer 1

Points

Question 2

Edges / arcs

Answer 2

Lines

Question 3

Weighted graph

Answer 3

Numbers associated with an edge

Question 4

Subgraph of graph G

Answer 4

Graph of G whose vertices belong to G and edges belong to G. A part of the original graph

Question 5

Degree / valency / order

Answer 5

Number of edges connected to node

Question 6

Walk

Answer 6

Route through the graph along the edges from one vertex to the next

Question 7

Path

Answer 7

A walk where no vertex is visited more than once

Question 8

Trail

Answer 8

A walk where no edge is visited more than once

Question 9

Cycle

Answer 9

A walk where the end vertex is the same as the start vertex and no other vertex is visited more than once

Question 10

Hamiltonian cycle

Answer 10

A cycle that includes every vertex

Question 11

Connected graph

Answer 11

A graph where all vertices are connected (directly or indirectly)

Question 12

Loop

Answer 12

Edge that starts and finishes at the same vertex

Question 13

Simple graph

Answer 13

No loops and at most 1 edge connected any pair of vertices

Question 14

Digraph (directed graph)

Answer 14

A graph where the edges have a direction associated with them

Question 15

Euler’s handshaking lemma

Answer 15

The sum of the degrees of the vertices is equal to 2x the number of edges

Question 16

Tree

Answer 16

A connected graph with no cycles

Question 17

Spanning tree

Answer 17

Subgraph which includes all the vertices of the original graph and is also a tree

Question 18

Complete graph

Answer 18

A graph in which every vertex is directly connected by a single edge to each of the other vertices

Question 19

Isomorphic graphs

Answer 19

Graphs which show the same information but are drawn differently

Question 20

Adjacency matrix

Answer 20

Describes the number of arcs joining the corresponding vertices

Question 21

Distance matrix

Answer 21

Describes the weight of each arc not the number of arcs

Question 22

Planar graph

Answer 22

A graph that can be drawn in a plane such that no two edges meet except at a vertex

Question 23

Minimum spanning tree

Answer 23

A spanning tree where the total weight of the arcs is as small as possible