CS202 Study Guide

7a. State the components of a graph

• What is the basic notion of a graph?
• What is the difference between graphs and trees?
• What is the difference between a directed and undirected graph?
• What are isomorphic graphs?

A basic graph consists of a nonempty set of vertices (nodes, elements), V, and a set of edges, E, which is a subset of the set V × V (every vertex connected to every other vertex). Note that although a set can be empty, a graph cannot exist without at least one vertex. However, a graph CAN exist without edges (links between nodes).

Graphs are a superset of trees and have applications in many domains, not just technical ones (for example, the management domain). We will talk more about trees in the next unit. For now, the difference between a graph and a tree is that (1) graphs have no unique root, while trees have a unique root; (2) graphs can have cycles, while trees cannot have cycles.

Directed and undirected graphs are the two most basic types. When an edge (path) exists between two nodes, a directed graph can only traverse the path in one direction. An undirected graph allows traversal in both directions.

Isomorphic graphs are bijective. There is a one-to-one correspondence between vertices and between edges. There are three features of isomorphic graphs:

1. The order of the graphs are the same, |V| = |V'|
2. The size of the graphs are the same, |E_V| = |E_V'|
3. They share the same degree of sequence, corresponding nodes have the same number of edges.

Review Basic Graph Theory and An Introduction to Graphs.

7b. Describe the two principal graph traversal paradigms

• What are the two main graph traversals discussed in this unit?
• Why are those two approaches important?
• What is one condition that must be met for the two main graph traversals to be accomplished?
• What is an n-cube? Draw an example.

There are two important methods of moving through (traversing) a graph, Eulerian and Hamiltonian. Both refer to undirected graphs. Eulerian traversals touch every edge but only once each. Hamiltonian traversals touch every vertex but only once each. For either traversal type to be used, the graph has to be fully connected, all vertices have to be part of one network. Not every graph is capable of Eulerian or Hamiltonian traversal. So, one cannot depend only on those. One can start designing that way as a means of gaining efficiency. But, to gain effectiveness, traversing the entire graph, one sometimes has to depart from pure Eulerian or Hamiltonian.

In the readings, there is a good example of a graph that does not have an Eulerian traversal, the well-known Koenigsberg Bridge Problem. A good example of a graph that does not have a Hamiltonian traversal is shown in Figure 1.

Figure 1. Example of graph for which there is no Hamiltonian traversal.

An n-dimensional hypercube is also called an n-cube. Basically, this is a graph that can be best visualized in multiple dimensions. The n-cube is typically denoted Qn, where n represents the number of dimensions. Two examples are shown in Figure 2.

Figure 2. Examples of multidimensional graph representations.

A brief application can be found in analog-to-digital conversion. In this case, the number of dimensions is 3, the number of bits used in the conversion. As the arrow moves across the dial of a gauge, it covers a special coating underneath. In so doing, it causes a binary string, a digital signal, to be sent to a computer. This string is interpreted within the computer as a way of converting the angle of the arrow into a 3-bit binary number. An adjacency of readings can be represented by a graph. This approach is illustrated in Figure 3.

Figure 3. Various representations of a 3-cube, Q3, and its use in analog-to-digital conversion.

Review Traversals: Eulerian and Hamiltonian Graphs.

7c. Explain the difference between directed and undirected graph

• What is a graph?
• Draw examples of directed and undirected graphs.
• What is a common notation for listing vertices and edges of graphs?
• What is "direction" an example of, relative to graphs?

As it says in our readings, "A graph is a formal mathematical representation of a network, which is itself a collection of objects connected in some fashion". There are two kinds of graphs, directed and undirected. Directed graphs have arrows to show possible transitions from one vertice (node) to another. If an arrow does not point from Node A to Node B, for instance, a transition from Node A to Node B is not allowed. On the other hand, an undirected graph has no directional arrows to indicate allowed transitions. The assumption is that transition is allowed along both directions of all edges. Figure 1 compares undirected and directed graphs. It also shows a common notation for listing a graph's vertices and edges.

Figure 1. Examples of undirected and directed graphs. Notice the common notation for Vertices (V) and Edges (E).

Direction of transition is one way of adding additional information to a graph. Another way is to show what is needed for a transition to take place in a system whose phases are represented by a graph. For instance, a number along an edge can be used to represent a variable's value that triggers a transition from one system phase (vertice) to a subsequent phase. This is illustrated in Figure 2.

Figure 2. Example of a graph being used to represent system states.

(Notice that there are two states to which the system could be initialized.)

Review Basic Graph Theory.

7d. Use graphs to solve applications involving associated events

• What is graph traversal optimization?
• Why do we care about graph-traversal optimization?
• What are some approaches to graph-traversal optimization?
• Is it reasonable to expect graph traversal to be perfectly optimized in practical situations?

Graph traversal refers to visiting each node in the network. Optimization refers to the cost or benefit of carrying out the traversal. All good planning aims for both efficiency and effectiveness. Efficiency leads to minimizing cost or maximizing benefit. Effectiveness refers to getting the task accomplished according to the task's requirements. It is insufficient to be efficient if effectiveness is not achieved.

Consider the undirected graph in Figure 1. It is but a simple example. Typical examples in reality are much larger, containing many more nodes and edges.

Figure 1. Weighted graph and its associated adjacency matrix.

W(X,Y) represents the weight assigned to the edge between nodes X and Y. Notice that, in this case,
W(X,Y) = W(Y,X), and that W(Y,Y) ≠ 0. The weight refers to the cost or benefit of moving from one node to another along that edge. In an example cost minimization task, we have to visit all nodes, one at a time, at minimum $\sum_{i=1}^{e} W i$, where e is the number of edges employed. For benefit optimization, we would want to maximize the summation. We can only visit a node by moving along an edge from an adjacent node. What can make this a difficult task is an increase in the number of nodes or the graph being directed so that it is not possible to move in both directions from one node to another. Further, it may be the case that not all nodes are connected to all other nodes. Brute-force optimization is not always possible given the time available.

There are various heuristics for optimizing graph traversals. The easiest is Nearest/Furthest Neighbor. If one wants to minimize the summation of weights, one follows the lowest-weighted edge to an adjacent unvisited node. To maximize, the highest-weighted edge is followed. That is the simplest description, but it does not say what to do when there are unvisited nodes in the graph but there are no unvisited nodes adjacent to the presently occupied node. At that point, one has to begin visiting nodes twice in an attempt to visit the remaining nodes.

Review Graph Optimization.

Unit 7 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• adjacency matrix
• adjacent
• bijective 
• directed graph 
• edges
• elements
• Eulerian traversals
• graph 
• graph traversal
• Hamiltonian traversals
• isomorphic graphs
• Koenigsberg Bridge Problem
• n-cube
• nodes
• optimization
• path
• superset
• trees 
• undirected graph 
• vertex
• vertices
  
• weighted graph