Quick Links:

VertexEdge Graph
A collection of vertices and edges, draw your own or create sample
vertexedge graphs. Add color, weight, and direction to a graph, run
tests and algorithms, and investigate the adjacency matrix representation
of a graph. 
VertexEdge Graphs
A vertexedge graph is a diagram consisting of a set of points (called
vertices) along with segments or arcs (called edges) joining some or all
of the points. The positions of the vertices, the lengths of the edges, and
the shape of the graph are not essential. Important features of a graph include
color,
weight,
direction, and how vertices are connected by edges.
Drawing VertexEdge Graphs
 Draw Vertices or Edges :
Select the button.
Draw a vertex by clicking once in the sketch area. To drawn an edge, hold
down the mouse button as you click and drag from the center of a vertex to
a new location in the sketch area (or to an existing vertex), release the
mouse button. Use these instructions as a guide for drawing a Simple
Graph, Multigraph, Directed
Graph, Weighted Graph, or Network.
Help Tip: Use the button
to select, edit, move, and make stylistic
changes to drawn vertices and edges.
 Simple Graph: A simple graph is a graph
that has at most one edge (i.e., either one edge or no edges) connecting
any two vertices.
 Multigraph: A multigraph is characterized
by vertices having more than one edge connecting them.
Help Tip: For two adjacent vertices (i.e., they are
already connected by an edge) use the tool
to add additional edges connecting them. When drawn, these edges will be
slightly bent.
See also bending edges.
 Directed Graph: A directed graph (or
digraph) is a graph where the edges have a direction that is indicated by
arrows.
Help Tip: Choose Options  Set Edge Type  Directed
before drawing edges or after drawn edges have been Selected .
 Weighted Graph: A weighted graph
has positive numerical values assigned to its edges.
Help Tip: To assign weight to individual edges, chose
the tool
and doubleclick on a drawn edge. Type a positive numerical value into
the text box then press Enter on the keyboard.
See also Weights.
 Network: A network is a Directed graph
with Weighted edges.
PreConstructed Graphs
Sample Graphs menu
This menu provides preconstructed vertexedge graph examples that are organized
based on graph type. When a graph is chosen, it will be displayed
in a separate window and may be edited and modified if desired. Some of the
options are described here:
 Complete: A complete graph is a connected
graph that has exactly one edge between every pair of vertices. Choose Sample
Graphs  Complete Graph to view an example of this type of graph.
Type a positive integer for the number of vertices to display in the graph
then click OK.
 Cycle: A cycle is a vertexedge graph consisting
of a single cycle  a route that uses each edge and vertex exactly once and
ends where it started. Choose Sample Graphs  Cycle to view an
example of this type of graph. Type a positive integer to specify the number
of vertices then click OK to display the graph.
 Complete Bipartite: A complete
bipartite graph, denoted Kn,m, is a graph consisting of
two sets of vertices, one with n vertices and the other with m vertices.
There is exactly one edge from each vertex in the one set to each vertex
in the other set. There are no edges between vertices within a set. Choose
Sample Graphs  Complete Bipartite to view an example of this type
of graph. Type two positive integers separated by a comma, (e.g. 2, 5), for
the number of vertices in each set then click OK.
 Random: Choose Sample Graphs  Random
to generate a random multigraph according to user specifications (with at
most two edges between any particular pair of vertices). First, type in a
positive integer for the number of vertices then click OK. Second, type a
number between 0.0 and 1.0 representing the probability that an edge should
be created.
 Peterson Graph: Choose Sample Graphs  Peterson
Graph to view this graph. One of the interesting features of the Peterson
graph is that it has an even number of vertices, all of which have odd degree.
 Euler Graph: An Euler graph is a vertexedge
graph that contains an Euler circuit. An Euler circuit has the property that
there is a path that uses each edge exactly once and the path starts
and ends at the same vertex. Choose Sample Graphs  Euler to view
an example of this type of graph.
 Not Euler Graph: A non Euler graph is a
graph that does not contain an Euler circuit. Choose Sample Graphs  Not
Euler Graph to view an example of this type of graph.
 Euler and Not Euler Generator:
Choose Sample Graphs  Euler and Not Euler Generator to view two
Euler graphs and two not Euler graphs at once.
Editing Graphs and Style Options
Once a vertexedge graph has been drawn (or selected from the Sample Graphs
menu) there are various style and edit options that you may choose to utilize.
As detailed below, the selection tool, Edit menu, and Options menus are the
prominent features available for editing graphs.
 Selecting Objects: Choose the Selection
Tool to select and move vertices
and edges once they have been drawn. This tool is also utilized for many
of the style and editing options available in the Options and Edit menus.
 When objects are selected, they will appear
highlighted.
 To select a single object, click on the object once.
 To add to or take away from an existing selection, hold down the Shift
key as you click on each object.
 To select all objects at once, press the "A" key together
with the Command key (Mac OS X) or Control key (Windows).
 To select a section or multiple objects in the sketch area, click in
a clear area and hold down the mouse button (your cursor will change
to a "+") as you drag a "box" around all desired
objects.
 To deselect all selected objects, click once in a clear area of the
window.
 Moving
Objects: Choose the button
to move vertices and to move and bend edges.
 Move a Vertex: Click in the center of a vertex and hold down
the mouse button as you move the mouse (and vertex) to a new location,
release the mouse button.
Note: Any edges that are connected to a vertex will stay
connected as it is moved.
 Move an Edge: To change the location or physical length of
an edge move the vertices that it is connected to.
 Bending Edges: To bend a drawn edge, hold down the Control
key (Mac OS X) or the Command key (Windows) as you click on the edge
that you want to bend. A small "repositioning box" will appear
where you clicked; select and drag this box to a new location to adjust
the curvature or bend of an edge.
Options menu
The Options menu offers various editing options to set edge type, vertex border,
and graph display. See the Adjacency Matrix section
for detailed help topics related to adjacency matrices.
 Add Loop to Vertices(s): A
loop is an edge that connects a vertex to itself. Select a
vertex (or multiple vertices) then choose Options  Add Loop to
Vertice(s).
 Set Edge Type: Use the Options  Set
Edge Type entry to set the edge type of drawn edges to be either Undirected
or Directed.
 Undirected: Undirected edges
do not indicate direction between vertices. In other words, the edges
do not have arrows on them. This is the default graph style.
 Directed: Directed
edges have arrows indicating direction from one vertex to another. Choose
Options  Set Edge Type  Directed, then all edges
drawn after this selection will be directed. Alternatively, Select undirected
edges that have already been drawn, then choose Set Edge Type  Directed
to show the direction on these edges. The direction is determined based
on how the graph is drawn.
Help Tip: To remove direction from drawn edges Select them
and choose Options  Set Edge  Undirected.
 Set Vertex Border: Use the Set Vertex
Border entry of the Options menu to set the type of border used for vertices.
 Circles: Choose Options  Set
Vertex Border  Circles to specify the shape of selected drawn
vertices to be circular. This is the default setting that will be automatically
applied to all new drawings.
 Rectangles: Choose Options  Set
Vertex Border  Rectangles to specify the shape of selected
drawn vertices to be rectangular.
 Set Graph Display: Use Options  Set
Graph Display entry to toggle the weight, color, and degree settings for
vertices and edges.
 Weights:
Weights are positive numerical values assigned to edges. Choose Options  Set
Graph Display  Weights to show (or hide) any user specified
or preconstructed weights. A checkmark next to this entry indicates
that any user specified or preconstructed weights will be shown  this
is the default setting.
 Name/Add Weight:
Choose the button
then doubleclick an edge, type text (to name) or numbers (to weight)
into the text box, then press Enter.
Help Tip: Add weight to drawn vertices by separating
any text and weight with a comma. For example, type Theme, 2 then press
Enter. This will be useful for creating your own digraphs to be used
with the Critical Path Algorithm.
 Colors:
Choose Options  Set Graph Display  Colors to show
(or hide) any user specified colors on a graph. A checkmark next to this
entry indicates that any user specified colors will be shown  this is
the default setting.
 Color Vertices or Edges :
To change the color of a vertex or edge to create a colored graph, follow
these steps: (1) Select the
object(s) you wish to color. (2) Choose the button
to view all color options. (3) Click on the desired color then click
OK to color all selected objects that color. Alternatively, perform Steps
23 then Step 1.
 Degrees:
Choose Set Graph Display  Degrees in the Options menu to view
(or hide) the degree of all vertices on a given graph. At least one vertex
must be drawn before choosing this option.
 Degree of a Vertex: The degree of a vertex is the number of
edges touching a vertex. If an edge loops back to the same vertex, that
counts as two edgetouchings.
Edit menu
The Edit menu offers stylistic options for existing graphs. Most menu options
are also available as toolbar buttons.
 Choose Edit  Undo to
reverse the most recent action that you performed. Subsequent execution of
this option will continue to reverse previous actions.
Note: Not all actions can be reversed using the undo feature
(e.g., the coloring of vertices or edges).
 Choose Edit  Redo to
reverse the action of the Undo button.
 Select an
object or objects that you would like to remove. Choose Edit  Cut
or the button
to remove the selected object(s).
 Choose Edit  Duplicate Graph to produce
an exact copy of the currently selected graph.
 Choose Edit  Tile All Windows or the button
to view all open windows at once.
Note: You cannot use the Undo option to reverse this
action, instead you must resize or use the Scaling Graphs feature as described
below.
 Scaling Graphs: To resize
or scale a window, use the dropdown menu in the bottom, righthand corner
and select a scale size. Available percentage options are: 25, 50, 75,
100, 200, 300, other.
Help Tip: The more windows that are open at one
time, the smaller they will each be scaled down when tiled, thus the
graphs on each window may be harder to see. It may be helpful to only
view four graphs at a time in this way.
 Alternative Graph Viewing Option:
When more than one window is open at a time, select which one you would
like to view by using the dropdown menu at the bottommiddle of the VertexEdge
Graph window. This drop down list contains the names of
all open windows.
Help Tip: The default window name is "Untitled," but
this changes to the file name you choose upon Saving.
File Options
The File menu offers options to open, save, and print new and existing work.
See Save & Print for help on Save,
Print, and Open options.
 New versus Clear
All: Choose File  New to create a separate blank window.
Alternatively, choose the Clear All button to
erase all drawn objects in the active window, without saving.
Note: Choosing File  New will not replace or clear any
previously drawn graphs in other windows.
 Open: Choose File  Open or the icon.
Select a previously saved VertexEdge Graph file and click Open.
 Close Window: Choose File  Close
to close the active window without saving. Alternatively, you may
use the close button (an "X")
on the title bar of an individual window to close it.
 Close All Windows: Choose File  Close
All to close all windows within VertexEdge Graph without saving.
 Choose File  Exit to quit the tools. Contents
of any open windows will be lost unless Saved first
Help Tip 1: To exit the VertexEdge Graph tool
without quitting the tools use the close button X.
Help Tip 2: To close individual windows within VertexEdge
Graph, choose Close or Close All in the File menu (or use the close
button X on each individual window).
Adjacency
Matrix
An adjacency matrix is a matrix representation of a vertexedge graph in which
each entry of the matrix indicates whether the corresponding pair of vertices
are connected by any edges (or rather, are adjacent). Each entry of the matrix
represents the number of directed edges connecting the row vertex to the column vertex.
A zero (0) indicates that the vertices are not adjacent.
 Display the Adjacency Matrix: Select
Options  Adjacency Matrix to show the adjacency matrix for the
drawn graph in a separate window. Click on the cells of this matrix to highlight
the corresponding edge(s) on the graph.
 Choose Options  Power of Adjacency
Matrix to calculate a specified power of the adjacency matrix for the drawn
graph. A message window will prompt you to enter the desired power that
you wish to compute, type a positive integer then click OK to view the
matrix in a separate window. Click on the cells of this matrix to highlight
the corresponding edge(s) on the graph.
 Choose Options  Distance Matrix
to view the distance matrix for a Weighted graph. Each cell of the matrix
represents the distance between the column vertex and row vertex. Click
on the cells of this matrix to highlight the corresponding edge(s) on the
graph.
 Choose Options  Paths of Length
n Matrix to display a matrix that shows the number of possible paths of
length n that go from the row vertex to the column vertex. Before you are
able to view the matrix, a message window will prompt you to enter the
desired path length; enter a positive integer value then click OK. Click
on the cells of this matrix to highlight the specified path on the graph
or to view all possible paths of length n (click on an entry of this list
to highlight the path on the graph).
 Choose Options  Adj Matrix to CAS to
show the adjacency matrix for the drawn graph in the CAS Home
and Y= tabs.
Tests & Algorithms
Tests menu
To test a drawn graph or network, choose an option from the Tests menu. A
separate message box will display the result of the test. If the test was successful,
the message box will list the appropriate vertices used for the chosen test.
 Connected: Choose Tests  Connected
to determine if the drawn graph is connected. A connected graph is a graph
that is all in one piece. That is, from each vertex there is at least one
path to every other vertex. If a graph is not connected, the message box
will specify how many connected components make up the graph. Additionally,
users can click on the dropdown bar to highlight an individual unconnected
component.
 Bipartite: Choose Tests  Bipartite
to determine if the drawn graph is bipartite. A bipartite graph has the property
that the vertices can be partitioned into two sets such that every edge connects
one vertex from each set. If a graph is bipartite, separate bipartite sets
will be highlighted. Additionally, users can choose to display the graph
with the bipartite sets separated.
 Euler: Choose Tests  Euler to determine
if an Euler circuit exists for the graph. An Euler circuit has the property
that there is a path that uses each edge exactly once and the path
starts and ends at the same vertex.
Help Tip: The Euler test will only display whether or
not the graph contains an Euler circuit, it will not tell you what the
Euler circuit is. Use the Euler Circuit Algorithm to display what the Euler
circuit is.
Algorithms menu
The Algorithms menu offers several different types of algorithms that can
be used after a graph or network is drawn. An algorithm is a list of stepbystep
instructions or a systematic stepbystep procedure. General instructions for
how to run an algorithm are provided below, followed by a list of possible
algorithms.
How to Run an Algorithm For a Drawn Graph:
 Choose Automatic or Step Through in the Algorithms menu to determine the
way the algorithm will be completed. A check mark will appear next to the
selected option.
 Automatic: Choose Automatic in the Algorithms
menu to automatically carry out and display the final result of the algorithm.
Important Note: The displayed result of an algorithm
may or may not be the only possible result.
 Step Through: Choose Step Through in the
Algorithms menu for the chosen algorithm to be implemented stepbystep
with user interaction.
Important Note: Messages with instructions may be
displayed in the lowerleft hand corner of the screen, or in separate
message windows.
 Select any of the available algorithms that are listed in the Algorithms
menu to perform that algorithm on the drawn graph.
Important Note: Be sure that only one type of procedure
and algorithm are selected at once; uncheck any unwanted options by clicking
on them.
 The chosen algorithm will run as Automatic or Step Through (depending on
the choice made in Step 1). See below for algorithmspecific help topics.
Algorithms
 Minimum Hamilton Circuit: A Hamilton
Circuit is a route through a graph that starts at one vertex, visits all
the others vertices exactly once, and finishes where it started. The purpose
of this algorithm is to find the shortest route (minimum total weight)
that meets the criterion of being a Hamilton Circuit.
 Automatic: The algorithm will automatically highlight the minimum
Hamilton Circuit on a graph. If there are two equivalent minimum circuits,
a new message window will appear with a drop down menu that will allow
you to show each highlighted circuit individually.
 List Hamilton Circuits: A Hamilton
Circuit is a path that begins and ends at the same vertex and that visits
each vertex of the graph exactly once. The purpose of this option is to
list all possible Hamilton Circuits of a particular graph. If available,
Hamilton Circuits will be organized in an interactive table by weight.
Click in the table to highlight a listed circuit on the graph. This option
will run the same and produce the same results regardless of whether the
Automatic or Step Through option is chosen.
 Nearest Neighbor: One purpose to using
the Nearest Neighbor algorithm is to find a minimum spanning tree, however,
this algorithm is not a guaranteed method for finding a minimum spanning
tree. In the Nearest Neighbor algorithm, choose a vertex to start at, and
successively add shortest edges without creating circuits, but only add
edges that are connected to the vertex where you are at each step.
 Automatic: The algorithm will automatically highlight a route through
the drawn graph and show the result of performing the algorithm in
a window. Messages will prompt you to consider whether every vertex
has been reached and whether the total weight is minimum. Each iteration
of this automatic algorithm may produce a different result, that may
or may not produce a minimum spanning tree.
 Step Through: You will first be prompted to click on a starting vertex
on the drawn graph, then select a valid minimum edge. Recall that you
must choose edges that are connected (adjacent) to the vertex that
you chose. When there are no more edges to be selected, the edge choices
and total weight will be displayed in a window. Messages will prompt
you to consider whether every vertex has been reached and whether the
total weight is minimum. Try starting at different vertices each time
you complete this step through algorithm to see what results.
 Kruskal's Minimum Spanning Tree: In Kruskal's "bestedge" algorithm,
you successively add shortest edges (of least weight) without creating
circuits, and any edge you add does not have to be connected to a previously
added edge. This algorithm is guaranteed to produce a minimum spanning
tree. Note that different runs of Kruskal's algorithm on the same graph
could produce different spanning trees.
 Automatic: The algorithm will automatically highlight a route through
the drawn graph and show the total weight of the highlighted edges
in a window. Recall that this may not be the only minimum spanning
tree for a particular graph.
 Step Through: Prompts in a message window will instruct you to first
select the edge with the least weight by clicking on it on the graph.
You will then continue in this manner, choosing the next "valid" edges
(as described above). When the chosen edges span the graph (without
creating a circuit), the total weight of the selected edges will be
displayed.
 Prim's Minimum Spanning Tree: In Prim's algorithm,
you start at a vertex and successively add shortest edges without creating
circuits, and any edge you add must be connected to any vertex already
reached. This algorithm is guaranteed to produce a minimum spanning tree.
Note that different runs of Prim's algorithm on the same graph could produce
different spanning trees.
 Automatic: The algorithm will highlight a possible route on the drawn
graph and display the total weight and order of chosen vertices in
a message window. Recall that the shown route may not be the only minimum
spanning tree for a particular graph.
 Step Through: A message window will prompt you to choose a starting
vertex by clicking on it on the graph. You will then be prompted to
click on "valid" edges (as described above). If you choose
an "invalid" edge, check the rules of the algorithm and try
again. When the chosen edges span the graph (without creating a circuit),
the total weight of the selected edges will be displayed.
 List Spanning Trees: A spanning tree
is a tree in a connected graph that reaches (i.e. includes or connects)
all the vertices in the graph. Note that a connected graph that has no
circuits is called a tree. The purpose of this option is to list all possible
spanning trees of a particular graph. All possible spanning trees will
be listed in an interactive table that lists the edges used (given by vertices;
e.g., {A,B} is the edge connecting vertices A and B). Click on a spanning
tree to highlight its path on the graph. This option will run the same
and produce the same results regardless of whether the Automatic or Step
Through option is chosen.
 Shortest Path: The purpose of this algorithm
is to determine the shortest path between two vertices. First Select two
vertices (and no edges), then choose Shortest Path in the Algorithms menu,
a message will display the shortest path as an integer value representing
the fewest number of edges required to get from one vertex to another.
The weight of this shortest path will be displayed once you click OK on
the first prompt window. This option will run the same and produce the
same results regardless of whether the Automatic or Step Through option
is chosen.
 Critical Path: A path through a Directed
graph (digraph) that corresponds to the earliest finish time is called
a Critical Path. Note that it is the length of the longest path that gives
the earliest finish time. A good sample graph to use for this algorithm
is the Feasibility Study Digraph, found in the Unit 6 Network Optimization
option of the Sample Graphs menu. Otherwise, create your own digraph with
weighted vertices by separating the text and weight with a comma.
 Automatic: The algorithm will automatically display the critical
path and the total weight of the critical path in a message window.
Also notice that the path will be highlighted on the drawn graph.
 Circuit Finder: A circuit is a path
which begins and ends at the same vertex. Note that a circuit does not necessarily
have to make use of every vertex or edge, nor is a circuit restricted to
using any particular vertex only once.
 Automatic: The algorithm will color the edges of each (partial) circuit
found. The user can then choose to view a partial circuit from the dropdown
list in the message box.
 Step Through: All edges will initially appear gray in color. Users
can click on any edge to show the associated partial circuit by coloring
all appropriate edges.
 Euler Circuit: If it is possible to
start at a vertex and pass along each edge without going over any of them
more than once, then the graph has an Euler path. If the path ends at the
same vertex at which you started, then it is called an Euler circuit.
 Automatic: The algorithm will automatically color partial circuits
in different colors, both on the graph and in a window with a colored
list of vertices. Additionally, an Euler circuit is then traced out by
stitching together the colored partial circuits.
 Step Through: The algorithm will display the partial circuits in different
colors on the graph and in a separate window with a colored list of vertices.
In another series of windows, click OK to see how all colored partial
circuits are stitched together as an Euler circuit is traced out sequentially.
 WelshPowell: The purpose of this algorithm
is to color each vertex starting with a vertex having the highest degree.
You then select another vertex of highest degree that is not connected to
the previous vertex. You continue doing this until you are required to switch
colors, and then the process starts over again.
 Automatic: The algorithm will automatically color the vertices on the
graph and display a window describing the minimum number of colors used
and the order in which they were chosen.
 Step Through: In the bottomleft corner of the main window, a message
will prompt you to select the next vertex. Select the appropriate vertices
in order according to the algorithm. The program will notify you when
a new color is needed for the coloring. The minimum number of colors
and an order will be displayed in a separate window when complete.
Help Tip: Choose Options  Degrees before
using this algorithm.