Definitions For Graphs and networks

Question 1

Walk

Answer 1

A route through a graph along edges

Question 2

Path

Answer 2

A walk where no vertex is visited more than once

Question 3

Trail

Answer 3

A walk where no edge is visited more than once

Question 4

Cycle

Answer 4

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

Question 5

A Hamiltonian cycle

Answer 5

A cycle including every vertex

Question 6

An Eulerian cycle/circuit

Answer 6

A trail which traverses every arc and starts and finishes at the same vertex

Question 7

Vertex set

Answer 7

List of vertexes

Question 8

Edge set

Answer 8

List of edges

Question 9

Degree or valency

Answer 9

Number of arcs/edges entering/incident to a vertex

Question 10

A simple graph

Answer 10

No loops (line starting and finishing at the same vertex) and at most 1 line connecting vertices

Question 11

Subgraph

Answer 11

A part of a graph

Question 12

Connected graph

Answer 12

Where every vertex is connected to another

Question 13

Digraph

Answer 13

A graph where edges have a direction specified

Question 14

Weighted graph

Answer 14

A graph where edges have a number assigned to them

Question 15

Tree

Answer 15

A tree is a connected graph with no cycles

Question 16

spanning tree

Answer 16

A spanning tree of a graph G is a sub graph which includes all the vertices but only some edges in order for it to be a tree

Question 17

A complete graph

Answer 17

Represented by Kn where n is number of vertices

A graph in which every vertex in connected by a single line to all other vertices

Question 18

Isomorphic graphs

Answer 18

Graphs which show the same information but can be drawn differently

Question 19

Adjacency matrix and graphs

Answer 19

Each entry in an adjacency matrix describes the number of arcs joining the corresponding vertices

Question 20

Distance matrices and graphs

Answer 20

In a distance matrix the entries represent the weight of each arc not the number of arcs

Question 21

Planar graph

Answer 21

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