Nm/Fragment 099 01

Typus Verschleierung

Bearbeiter Hindemith

Gesichtet

Untersuchte Arbeit: Seite: 99, Zeilen: 1-25

Quelle: Borgatti_2002 Seite(n): 3-4, Zeilen: p3: 13ff; p4: 1ff

A walk in which no edge occurs more than once is known as a trail. In Figure 3.1, the sequence a, b, c, e, d, c, g is a trail but not a path. Every path is a trail, and every trail is a walk. A walk is closed if $v_o = v_n$. A cycle can be defined as a closed path in which n >= 3. The sequence c, e, d in Figure 3.1 is a cycle. A tree is a connected graph that contains no cycles. In a tree, every pair of points is connected by a unique path. That is, a tree is a graph in which any two vertices are connected by exactly one path. The length of a walk (and therefore a path or trail) is defined as the number of edges it contains. For example, in Figure 3.1, the path a, b, c, d, e has length 4. A walk between two vertices whose length is as short as any other walk connecting the same pair of vertices is called a geodesic. Of course, all geodesics are paths. Geodesics are not necessarily unique. From vertex a to vertex f in Figure 3.1, there are two geodesics: a, b, c, d, e, f and a, b, c, g, e, f. The graph-theoretic distance (usually shortened to just “distance”) between two vertices is defined as the length of a geodesic that connects them. If we compute the distance between every pair of vertices, we can construct a distance matrix D such as depicted in Figure 3.3. The maximum distance in a graph defines the graph’s diameter. As shown in Figure 3.3, the diameter of the graph in Figure 3.1 is 4. If the graph is not connected, then there exist pairs of vertices that are not mutually reachable so that the distance between them is not defined and the diameter of such a graph is also not defined.

A walk in which no edge occurs more than once is known as a trail. In Figure 3, the sequence a, b, c, e, d, c, g is a trail but not a path. Every path is a trail, and every trail is a walk. A walk is closed if $v_o = v_n$. A cycle can be defined as a closed path in which n >= 3. The sequence c, e, d in Figure 3 is a cycle. A tree is a connected graph that contains no cycles. In a tree, every pair of points is connected by a unique path. That is, there is only one way to get from A to B. The length of a walk (and therefore a path or trail) is defined as the number of edges it contains. For example, in Figure 3, the path a, b, c, d, e has length 4. A walk between twovertices whose length is as short as any other walk connecting the same pair of vertices iscalled a geodesic. Of course, all geodesics are paths. Geodesics are not necessarily unique. From vertex a to vertex f in Figure 1, there are two geodesics: a, b, c, d, e, f and a, b, c, g, e, f. The graph-theoretic distance (usually shortened to just “distance”) between two vertices is defined as the length of a geodesic that connects them. If we compute the distance between every pair of vertices, we can construct a distance matrix D such as depicted in Figure 4. The maximum distance in a graph defines the graph’s diameter. As shown in [page 4] Figure 4, the diameter of the graph in Figure 1 is 4. If the graph is not connected, then there exist pairs of vertices that are not mutually reachable so that the distance between them is not defined and the diameter of such a graph is also not defined.

Anmerkungen No source given, very minor adjustments

Sichter (Hindemith), WiseWoman