Help Topics Custom Apps Save & Print Index Catalog

 Vertex-Edge Graph A collection of vertices and edges, draw your own or create sample vertex-edge graphs. Add color, weight, and direction to a graph, run tests and algorithms, and investigate the adjacency matrix representation of a graph.

Vertex-Edge Graphs

A vertex-edge 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 Vertex-Edge 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.

• 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 double-click on a drawn edge. Type a positive numerical value into the text box then press Enter on the keyboard.

• Network: A network is a Directed graph with Weighted edges.

Pre-Constructed Graphs

This menu provides pre-constructed vertex-edge 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 vertex-edge 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 vertex-edge 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 vertex-edge 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.

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 pre-constructed weights. A checkmark next to this entry indicates that any user specified or pre-constructed weights will be shown - this is the default setting.
• Name/Add Weight: Choose the button then double-click 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 2-3 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 edge-touchings.

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 drop-down menu in the bottom, right-hand 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 drop-down menu at the bottom-middle of the Vertex-Edge 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 Vertex-Edge 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 Vertex-Edge 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 Vertex-Edge Graph tool without quitting the tools use the close button X.

Help Tip 2: To close individual windows within Vertex-Edge Graph, choose Close or Close All in the File menu (or use the close button X on each individual window).

An adjacency matrix is a matrix representation of a vertex-edge 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

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 drop-down 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.

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 step-by-step instructions or a systematic step-by-step 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:

1. 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 step-by-step with user interaction.
Important Note: Messages with instructions may be displayed in the lower-left hand corner of the screen, or in separate message windows.
2. 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.
3. The chosen algorithm will run as Automatic or Step Through (depending on the choice made in Step 1). See below for algorithm-specific 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 "best-edge" 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 drop-down 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.
• Welsh-Powell: 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 bottom-left 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.