3-1-7 Graph Theory

The undirected panel has vertices V1 through V5 and edges E1 through E6. Its edges join V1-V2 (E1), V1-V3 (E2), V2-V3 (E3), V3-V4 (E4), V3-V5 (E5), V4-V5 (E6). The directed panel has V1 through V4 and E1 through E5: E1 points V1 to V2; E2 V1 to V4; E3 V2 to V3; E4 V2 to V4; E5 V3 to V4. All original vertex and edge indices are lower indices.

[Example of an undirected graph] [Example of a directed graph] V = {V1, V2, V3, V4, V5} V = {V1, V2, V3, V4} E = {E1, E2, E3, E4, E5, E6} E = {E1, E2, E3, E4, E5}

The four source definitions and examples appear in order Trail, Path, Circuit and Cycle. Their full printed vertex/edge sequences are transcribed below in exactly that order, retaining every repeated vertex and original lower index.

• Trail: A walk with all different edges. [Example] (V1, E2, V3, E4, V4, E6, V5, E5, V3) • Path: A walk with all different vertices. [Example] (V1, E1, V2, E3, V3, E5, V5) • Circuit: A trail in which the start and end vertices are the same. [Example] (V1, E2, V3, E5, V5, E6, V4, E4, V3, E3, V2, E1, V1) • Cycle: A path in which the start and end vertices are the same. [Example] (V1, E1, V2, E3, V3, E2, V1)

The source matrix and adjacent labelled array have row/column order V1,V2,V3,V4,V5. Their five rows are (0,E1,E2,0,0); (E1,0,E3,0,0); (E2,E3,0,E4,E5); (0,0,E4,0,E6); (0,0,E5,E6,0). All E numbers and V labels are lower indices. Both original representations remain together.

V1 V2 V3 V4 V5 V1 0 E1 E2 0 0 V2 E1 0 E3 0 0 V3 E2 E3 0 E4 E5 V4 0 0 E4 0 E6 V5 0 0 E5 E6 0

The Types of graphs box contains the definitions of Tree, Complete graph and Eulerian graph. Its tree has six unlabelled vertices, its complete graph has four vertices and all six edges, and its Eulerian graph has labelled vertices A through H. The example of a single stroke reads A→B→G→D→B→C→F→E→C→D→H→G→A.

[Types of graphs] • Tree This is a type of undirected graph with no closed path. • Complete graph This is a connected graph in which all different vertices are connected as a single edge. • Eulerian graph This is an undirected graph that can be drawn with a single stroke. If the start and end vertices are the same, all vertices must have an even number of connected edges. Complete graph Tree Eulerian graph

The original diagram has five unlabelled circular states: a leftmost state, a second lower state, an upper state, a third lower state and a rightmost state. Arrows connect the leftmost state to the second; the second and upper states in both directions; the upper state to the third lower state; the second and third lower states in both directions; and the third lower and rightmost states in both directions. Self-loops appear at the leftmost, third lower and rightmost states. The original caption is Figure 1-7 State transition diagram.

Figure 1-7 State transition diagram