8.04 Walks and paths

For each of the following networks, state a valid walk that crosses each vertex once:

a

b

State the definition of a path in regard to graph theory.

Consider the given network:

a

State whether the following are valid walks:

i

K, F, P, K

ii

K, P, F, K, P

iii

K, P, F, R, M

iv

R, P, F, M, R

v

K, P, F, K

vi

F, R, M, P, F

b

State whether the following are valid paths:

i

K, P, F, R, M

ii

K, P, F, K, P

iii

K, P, F, K

For each of the following graphs, state whether each list of vertices defines a valid path:

a

i

E, D, C

ii

D, A, C

iii

E, F, C

iv

A, B, D

v

A, B, C

b

i

C, D, D

ii

D, C, D

iii

A, B, C

iv

B, C, A

v

A, D, C

c

i

A, B, C

ii

E, D, C

iii

B, C, C

iv

D, E, A

v

B, A, B

d

i

E, D, B

ii

A, E, C

iii

E, C, B

iv

A, D, C

v

B, A, E

e

i

A, B, D, G, F

ii

A, B, C, D, G, E

iii

D, B, A, C, F, G

iv

E, B, D, C, A

f

i

A, B, C, D, G, E

ii

E, F, G, H, D, B

iii

C, E, F, D, G, C

iv

A, B, D, H, G, C

g

i

A, C, E, D, B

ii

E, C, B, D, A

iii

B, C, D, E, A

iv

D, A, B, C, E

State a path that satisfies the given information for each of the following networks:

a

The path starts at B and ends at X.

b

The path starts at H, goes through 4 other vertices, and then ends at B.

c

The path starts at Q, has length 3, and ends at P.

d

The path starts at P and ends at Q

Define the following terms in relation to graph theory:

For each of the following lists, select the odd one out and explain your choice:

State whether each of the following graphs is connected:

a

b

c

d

Consider the following graph:

a

How many edges are connected to vertex \\A?

b

List the vertices adjacent to vertex E.

c

State the vertex directly connected to all other vertices.

d

Which vertex is not directly connected to vertex A?

For each of the given networks, determine if the listed vertices define a valid circuit:

a

i

C, B, A, E, D, C

ii

B, A, E, C, D, B

iii

B, C, A, E, D, C

iv

D, C, B, A, E, D

b

i

C, E, F, D, B, A, C, G

ii

C, E, F, G, H, D, C

iii

A, B, D, H, G, C, A

iv

E, F, G, H, D, B, E

c

i

F, C, D, B, E, G, F

ii

E, B, A, C, D, G

iii

G, D, C, F, E, B, G

iv

A, B, D, C, F, A