Basic Terminology Homework Help, Assignment Help, Online Tutor, Tutoring

Submit Assignment

* *

Payment Online Assignment Help

Trigonometry Homework

Homework Help

sfsf

Basic Terminology

A directed graph G is defined abstractly as an ordered pair (V, E), where V is a set and E is a binary relation on V. As was pointed out before, a directed graph can be represented geometrically as a set of marked points V with a set of arrows E between pairs of points. The elements in V are called the vertices, and the ordered pairs in E are called the edges of the directed graph. An edge is said to be incident with the vertices it joins. For example, the edge (a, b) is incident with the vertices a and b. Sometimes, when we wish to be more specific, we say that the edge (a, b) is incident from a and is incident into b. The vertex a is called the initial vertex, an the vertex b is called the terminal vertex of the edge (a, b). An edge that is incident from and into the same vertex, like (c, c) is called a loop. Two vertices are said to be adjacent if they are joined by an edge. Moreover, corresponding to an edge (a, b), the vertex a is said to be adjacent to the vertex b, and the vertex b is said to be adjacent from the vertex a. A vertex is said to be an isolated vertex if there is no edge incident with it.

An undirected graph G is defined abstractly as an ordered pair (V, E), where V is a set and E is a set multisets of two elements from V. For example, G = ({a, b, c, d}, {{a, b}, {a, d}, {b, c}, {b, d}, {c, c}}) is an undirected graph. An undirected graph can be represented geometrically as a set of marked points V with a set of lines E between the points. As another example, let V = {a, b, c, d, e} be a set of computer programs. An undirected graph in which there is an edge between two vertices if the corresponding programs share some common data is the graph of this type. From now on, when it is clear from the context, we shall use the term graph to mean either a directed graph, or an undirected graph, or both.

Let V = {a, b, c, d} be the four players in a round-robin tennis tournament. Let E = {{a, b}, {a, d}, {c, a}, {d, c}} be a binary relation on V so that (x, y) in E means that x beats y in the match between them. The graph G = (V, E). Let V’ = {1, 2, 3, 4} be the four chapters in a book. Let E’ = {(1, 2), (2, 3), (3, 1), (3, 4), (4, 1), (4, 2) be a binary relation on V’ such that (1, 2) in E’ means that the material chapter 1 refer to that in chapter 2, and so on. A careful reader might have recognized that the graph “resembles” the other graph. Indeed, such a “resemblance” becomes even more evident if we redraw the graph. Two graphs are said to be isomorphic if there is a one-to-one correspondence between their vertices and between their edges such that incidences are preserved. In other words, there is an edge between two vertices in one graph if and only if there is a corresponding vertices in the other graph.