Chapter 15 Graph Theory

Question 1

Graph

Answer 1

Structure which shows the physical connection or relationship between things of interest

Question 2

Vertices

Answer 2

Points on graphs

Question 3

Edges

Answer 3

Way to move from one vertex to another

Question 4

Loop

Answer 4

an edge from one vertex to itself

Question 5

Adjacent vertices

Answer 5

vertices connected by an edge

Question 6

Adjacent edges

Answer 6

edges which share a common vertex

Question 7

Degree

Answer 7

number of edges connected to a vertex

Question 8

Undirected graph

Answer 8

allowed to move on either direction on an edge

Question 9

Directed graph

Answer 9

Contain arrows indicating the directions allowed to move in

Question 10

In degree

Answer 10

Of a vertex the number of edges coming into the vertex

Question 11

Out degree

Answer 11

Of a vertex the number of edges going out from the vertex

Question 12

Simple graph

Answer 12

no loops, maximum one edge joining any pair of distinct vertices

Question 13

Subgraph

Answer 13

made from subset of vertices and edges within a graph

Question 14

Connected graph

Answer 14

Undirected, possible to travel from every vertex to every other vertex by following edges

Question 15

Disconnected graph

Answer 15

not possible to travel from every vertex to every other vertex by following edges

Question 16

Strongly connected graph

Answer 16

Directed graph, possible to travel from every vertex to every other vertex by following the edges in the right direction

Question 17

Weighted graph

Answer 17

Has numbers assigned to edges that represent a certain weight

Question 18

Weighted adjacency table

Answer 18

Used to summarise the weights on a graph

Question 19

Complete graph

Answer 19

simple undirected graph, in which every vertex is connected to every other vertex by an edge