CH7: NETWORKS [VOCAB]

Question 1

nodes/vertices

Answer 1

points on a network

Question 2

edge

Answer 2

a line joining to nodes or vertices

Question 3

faces/regions

Answer 3

edges divide a graph up into seperate sections

Question 4

loop

Answer 4

an edge that starts and ends at the same vertex

Question 5

multiple edges

Answer 5

two or more edges that connect the same two vertices

Question 6

weighted graph/network

Answer 6

graphs that have amounts or distances or some information on each edge

Question 7

directed edges/arcs

Answer 7

an edge with significant direction shown with an arrow

Question 8

directed graph/network or digraph

Answer 8

any graph involving directed edges (1 or more)

Question 9

undirected graph/network

Answer 9

any graph with no directed edges

Question 10

simple graph/network

Answer 10

a graph or network with no loops, multiple edges or direction, no crossovers

Question 11

walk

Answer 11

a sequence of edges joined by vertices

Question 12

open walk

Answer 12

a walk which does not start and end at the same vertex

Question 13

closed walk

Answer 13

a walk which starts and ends at the same vertex

Question 14

open path

Answer 14

a walk that has no repeats of edges or vertices and does not start and end at the same vertex

Question 15

closed path or ‘cycle’

Answer 15

a walk that has no repeats of edges or vertices and starts and ends at the same vertex

Question 16

path length

Answer 16

the number of edges a walk, path or cycle uses

Question 17

trail

Answer 17

a walk with no repeated edges (may have repeated vertices)

Question 18

connected graph

Answer 18

an undirected graph where every vertex is connected to each other

Question 19

disconnected/unconnected graph

Answer 19

a graph where a vertex is not joined by an edge

Question 20

complete graphs

Answer 20

simple graphs in which every vertex is connected to every other

Question 21

bridge

Answer 21

any edge which, when removed, causes a network to become disconnected

Question 22

degree/order

Answer 22

the number of edges that meet a vertex

Question 23

isolated vertex

Answer 23

a vertex not connected to an edge

Question 24

planar graphs

Answer 24

networks that can be drawn without edges crossing over

Question 25

null graphs

Answer 25

networks made up of no edges, just isolated vertices

Question 26

trivial graphs

Answer 26

networks that have only one vertex (null graphs)

Question 27

subgraph

Answer 27

a smaller section of the original graph

Question 28

platonic solid

Answer 28

the ‘net’ of a 3D shape where each face is the same regular polygon

Question 29

traversable

Answer 29

refers to a connected graph with 0 odd vertices or exactly 2 odd vertices

Question 30

eulerian trail

Answer 30

travels every edge once, may repeat vertices, 0 odd vertices, starts and finishes at the same vertex

Question 31

semi-eulerian

Answer 31

• connected graph
• open trail
• includes every edge only once
• contains 2 odd vertices
• starts and finishes at the same point

Question 32

adjacent vertices

Answer 32

vertices that share a common edge

Question 33

in-degree

Answer 33

number of edges coming into a vertex

Question 34

out-degree

Answer 34

number of edges coming out of a vertex

Question 35

bipartite graph

Answer 35

a graph in which the vertices can be split into two groups

Question 36

complete bipartite graph

Answer 36

a bipartite graph that has every member of one group connected to every member of the other group

Question 37

euler’s formula

Answer 37

v + f - e = 2

Question 38

circuit

Answer 38

a closed trail. a trail that starts and ends at the same vertex.

Question 39

path

Answer 39

a walk if it includes no repeated use of an edge and no repeated use of a vertex, (except for the vertex we started from)

Question 40

0 odd vertices

Answer 40

.

Question 41

2 odd vertices

Answer 41

.

Question 42

hamiltonian path

Answer 42

path that cuts through every vertex

Question 43

hamiltonian cycle

Answer 43

type of hamiltonian graph that starts and ends at the same vertex

Question 44

semi-hamiltonian graph

Answer 44

.