슬라이드

Jong C. Park
Computer Science Division,
Today’s TopicsIntroductionPaths and CyclesHamiltonian Cycles and the Traveling Salesperson ProblemA Shortest-Path AlgorithmRepresentations of GraphsIsomorphisms of Graphs GRAPH THEORY
– a cycle in a graph G that contains each vertex in G exactly once, except for the starting and ending – Determine if the following graphs have a • the graph of Figure 8.3.4• the graph of Figure 8.3.5• the graph of Figure 8.3.6• the graph of Figure 8.3.7 – Given a weighted graph G, find a minimum-length – When can an n-cube simulate a ring model with 2n – Equivalently, when does an n-cube contain a – The n-cube has a Hamiltonian cycle if and only if n  2 and there is a sequence, s1, s2, ., s2n, where each si is a string of n-bits, satisfying: • Every n-bit string appears somewhere in the sequence.
• si and si+1 differ in exactly one bit, i = 1, ., 2n-1.
• s2n and s1 differ in exactly one bit.
– The sequence above is called a Gray code.
– When n  2, a Gray code corresponds to the Hamiltonian cycle s1, s2, ., s2n, s1.
– Let G1 denote the sequence 0, 1. We define Gn in (a) Let GRn-1 denote the sequence Gn-1 written in reverse.
(b) Let G’n-1 denote the sequence obtained by prefixing each (c) Let G’’n-1 denote the sequence obtained by prefixing each (d) Let Gn be the sequence consisting of G’n-1 followed by Then Gn is a Gray code for every positive integer n.
• The proof is done by induction on n.
– The n-cube has a Hamiltonian cycle for every – Construct the Gray code G3 beginning with G1– The Knight’s Tour • A knight’s tour of an n x n board begins at some square, visits each square exactly once making legal moves, and • The problem is to determine for which n a knight’s tour – Dijkstra’s shortest-path algorithm correctly finds the length of a shortest path from a to z.
– Find a shortest path from a to z and its length for – For input consisting of an n-vertex, simple, connected, weighted graph, Dijkstra’s algorithm has – Select an ordering of the vertices, say a, b, c, d, e.
– Label the rows and columns of a matrix with the – The entry in this matrix in row i, column j, i  j, is the number of edges incident on i and j. If i = j, the entry is twice the number of loops incident on i.
– The degree of a vertex v in a graph G is obtained by summing row v or column v in G’s adjacency – If A is the adjacency matrix of a simple graph, the ijth entry of An is equal to the number of paths of length n from vertex i to vertex j, n = 1, 2, . .
– We label the rows with the vertices and the columns with the edges (in some arbitrary order). – The entry for row v and column e is 1 if e is incident on – Find the incidence matrix for the graph of Figure 8.5.4.
– In a graph without loops, each column has two 1’s and the sum of a row gives the degree of the vertex – Graphs G1 and G2 are isomorphic if there is a one- to-one, onto function f from the vertices of G1 to the vertices of G2 and a one-to-one, onto function g from the edges of G1 to the edges of G2, so that an edge e is incident on v and w in G1 if and only if the edge g(e) is incident on f(v) and f(w) in G2. – The pair of functions f and g is called an – Define an isomorphism for the graphs G1 and G2 of – The Mesh Model for Parallel Computation • The two dimensional mesh model for parallel computation when described as a graph consists of a rectangular array • When can an n-cube simulate a two-dimensional mesh?• When does an n-cube contain a subgraph isomorphic to a • If M is a mesh p vertices by q vertices, where p ≤ 2i and q ≤ 2j, then the (i+j)-cube contains a subgraph isomorphic – Graphs G1 and G2 are isomorphic if and only if for some ordering of their vertices, their adjacency – Let G1 and G2 be simple graphs. The following are (b) There is a one-to-one, onto function f from the vertex set of G1 to the vertex set of G2 satisfying the following: Vertices v and w are adjacent in G1 if and only if the vertices f(v) and f(w) are adjacent in G2.
– Determine if G1 and G2 in Figure 8.6.1 are isomorphic by examining their adjacency matrices.
– A property P is an invariant if whenever G1 and G2 If G1 has property P, G2 also has property P. • “has e edges”• “has n vertices” – Use the notion of an invariant to determine if the graphs G1 and G2 in Figure 8.6.3 are isomorphic.
– Show that if k is a positive integer, “has a vertex of – Suppose G1 and G2 are isomorphic graphs and f (resp., g) is a one-to-one, onto function from the vertices (resp., edges) of G1 onto the vertices (resp., edges) of G2. – Suppose further that G1 has a vertex v of degree k. – Use the fact that “has a vertex of degree 3” is an invariant to determine if the graphs G1 and G2 in – Show that if k is a positive integer, “has a simple cycle of length k” is an invariant.
– Use the fact that “has a simple cycle of length 3” is an invariant to determine if the graphs G1 and G2 of • Paths and Cycles• Hamiltonian Cycles

Source: http://nlpcl.kaist.ac.kr/~cs204/lecture15.pdf