graph definitions

Question 1

define graph:

Answer 1

vertices connected by edges

Question 2

define network:

Answer 2

a weighted graph

Question 3

define subgraph:

Answer 3

part of a graph

Question 4

define degree:

Answer 4

number of vertices connected to a specified one

Question 5

define valency:

Answer 5

number of vertices connected to a specified one

Question 6

define order:

Answer 6

number of vertices connected to a specified one

Question 7

define walk:

Answer 7

a route along the edges of a graph

Question 8

define path:

Answer 8

a walk that repeats no vertices

Question 9

define trail:

Answer 9

a walk that repeats no edges

Question 10

define cycle:

Answer 10

a path that returns to the starting vertex

Question 11

a hamiltonian cycle:

Answer 11

a cycle that includes every vertex

Question 12

define simple graph:

Answer 12

a graph with no loops and with at most one edge connecting any pair of vertices

Question 13

define digraph:

Answer 13

a directed graph

Question 14

define euler’s handshaking lemma:

Answer 14

in an undirected graph, the sum of the degrees of the vertices = twice the number of edges, so the number of odd vertices must be even

Question 15

define tree:

Answer 15

a connected graph with no cycles

Question 16

define spanning tree:

Answer 16

a tree containing all the vertices

Question 17

define complete graph:

Answer 17

a graph where every vertex is connected to every other vertex

Question 18

define isomorphic graphs:

Answer 18

graphs that have the same edges and vertices that connect in the same way, but are drawn differently

Question 19

define eulerian graph:

Answer 19

a graph that contains a trail that includes every vertex and edge and returns to the starting vertex (connected graphs with even vertices always are)

Question 20

define semi-eulerian graph:

Answer 20

a graph that contains a trail that includes every vertex and edge and ends on a different vertex to the starting one (connected graphs with one pair of odd vertices always are)