Graphs/Trees: For each of the following, draw a graph following the specificatio
ID: 3860304 • Letter: G
Question
Graphs/Trees: For each of the following, draw a graph following the specifications or explain why no such graph exists Tree, five vertices, total degree 8. Simple graph, connected, six vertices, six edges. Graph, two vertices, one edge, not a tree. Isomorphism of Graphs: In 1953, the CIA managed to photograph a KGB document listing their agents in a large third-world city, showing their past operations, duties, and contacts among themselves. Unfortunately, it listed the agents by the code designations D through L. The documents shows that agents D's contacts were F and L; E's were J and K; F's were D, J and L; G's were I an L; H's were I and J, I's were G, H and K; J's were E, F and H; K's were E and I; and L's were D, F and G. Draw an edge between agents if they are contacts. Call the graph A. Unfortunately, the information in the document is of little use without the identities of the agents. An inquiry to the CIA office in this city reveals that the suspected agents there were Telyanin, Rostov, Lavrushka, Karugin, Ippolit, Willaski, Dolokhov, Balashev and Kutuzov. Examining records of past meetings, the CIA created the contact graph C (represented below)Explanation / Answer
A finite simple graph G consists of a set of vertices V, with |V| = n, and a set of edges E, such that each edge is an unordered pair of distinct vertices. The definition of a simple graph G forbids loops (edges joining a vertex to itself) and multiple edges (many edges joining a pair of vertices), whence the set E must also be finite, with |E| = m. We label the vertices of G with the integers 1, 2, ..., n. If the unordered pair of vertices {u, v} is an edge in G, we say that u is adjacent to v and write uv E. Adjacency is a symmetric relationship: uv E if and only if vu E. The degree of a vertex v is the number of vertices that are adjacent to v. A (u, v)-path P in G is a sequence of distinct vertices u = v1, v2, ..., vk = v such that vivi+1 E for i = 1, 2, ..., k-1. If such a (u, v)-path P exists, then the vertices u and v are said to be connected by a path of length k-1.
Given any pair of vertices (u, v) in G, we define the distance
d(u, v) = 0, if u = v,
d(u, v) = the length of a shortest (u, v)-path, if u and v are connected, and
d(u, v) = , otherwise.
We now introduce the key ingredients of semiotic theory. For any pair of vertices (u, v) in G, the collateral graph Guv is defined as follows:
If uv E, then Guv is obtained by deleting the edge uv from G while preserving all the vertices of G. We use the binary sign + to distinguish the distance function in this case.
If uv E, then Guv = G. We use the binary sign to distinguish the distance function in this case.
The pair graph Guv for any pair of vertices (u, v) in G is defined as follows:
w is a vertex of Guv if and only if w belongs to a shortest (u, v)-path in Guv, and
wx is an edge of Guv if and only if wx is also an edge of G.
For any pair of vertices (u, v) in G, we write the (u, v)-sign, denoted by the symbol suv, as follows:
suv = ± duv . nuv . muv
where
the leading binary sign is positive if uv E, or negative if uv E;
duv is the distance d(u, v) in the collateral graph Guv ;
nuv is the number of vertices of the pair graph Guv;
muv is the number of edges of the pair graph Guv.
The sign matrix S of the graph G is written as an n × n array with the (u, v)-sign suv as the entry in row u and column v,
S = [ suv ] .
The adjacency matrix of G is an n × n matrix with the entry in row u and column v equal to 1 if uv E and equal to 0 if uv E. Thus, the adjacency matrix of the graph G can be recovered from the leading binary signs of the entries of the sign matrix S. Note that for a simple graph G, both the adjacency matrix and the sign matrix S are symmetric.
We shall now define a canonical form S* of the sign matrix by ordering the rows and columns of S in a certain way. First, write the set of all distinct (u, v)-signs suv in lexicographic order s1, s2, ..., sr. Then, for each row i of the sign matrix, i = 1, 2, ..., n, compute the sign frequency vector
fi = ( fi(1), fi(2), ..., fi(r) )
where fi(k) is the number of times the sign sk occurs in row i. Since S is symmetric, the sign frequency vector for column i is the same as the sign frequency vector for row i, for i = 1, 2, ..., n. Now, write the sign frequency vectors f1, f2, ..., fn in lexicographic order fi1, fi2, ..., fin. Reorder the rows and columns of the sign matrix according to the permutation i1, i2, ..., in of the vertices 1, 2, ..., n of G to obtain the canonical form S* of the sign matrix.
The vertices of G are partitioned into equivalence classes consisting of vertices with the same sign frequency vectors. Thus, the canonical form S* of the sign matrix is uniquely defined only upto permutations of vertices within each equivalence class.
Graphs GA and GB are said to be isomorphic if there exists a bijection
: VA VB
from the vertices of graph GA to the vertices of graph GB, such that uv is an edge in graph GA if and only if (u)(v) is an edge in graph GB. The graph isomorphism problem is to determine whether two given graphs are isomorphic or not.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.