Having introducted graphs, the language of graphs, and several examples of important graphs, we look at two ideas in this section. First we will look at different ways to represent graphs: as adjacency lists, adjacency matrices, incidence matrices, and as dictionaries. Second, with these different means of representing graphs we will look at graph isomorphism which is a way of saying whether two graphs are "the same" even if they are laid out differently.
- CC.17: State the definitions of the following terms: Isomorphic graphs; isomorphism of graphs.
- CC.18: Given a graph represented as an adjacency list, Python dictionary, adjacency matrix, or incidence matrix, determine whether two nodes are connected and calculate the degree of a node.
- M.16 (CORE): Given a graph represented as an adjacency list, Python dictionary, adjacency matrix, or incidence matrix, write it in one of the other representations and use the representation to determine information about the graph.
- M.17: Determine whether two graphs are isomorphic; if they are, state the isomorphism.
For basic preparation, please read all of Section 9.3 in the Rosen textbook. Focus especially on definitions of terminology; working through examples (particularly the examples on representation of graphs); and Examples 8, 9, and 10 regrading isomorphism.
As always, work out the activities below in your notes for future reference and questions. Then go to the submission form at:
and put your answers in the indicated areas. There is a link to a Google Form at which you can leave and upvote any questions you have on what you've read and worked with; your answers will help set the agenda for the class meeting.
(1) Open up a Sage worksheet and enter in the following. You'll need to scroll to the right to get the entire first line.
adjacency_dictionary = {'a':['b', 'c', 'e'], 'b':['a'], 'c':['a','d','e'], 'd':['c','e'], 'e':['a','c','d']}
example1 = Graph(adjacency_dictionary)
example1.show()
Once the graph is plotted, compare it to the graph from Example 1 in Section 9.3. Are these two graphs "the same"? Also, how is the dictionary given above similar to the adjacency list that is presented in Example 1?
Before moving on to exercise 2, do the following -- not to turn in, but just to familiarize yourself with using Sage for the operations in this section:
example1.adjacency_matrix()
example1.incidence_matrix()
Notice that the incidence matrix is a little differently made than what's described in your book. For your private consideration, not to turn in: What do you think the negative signs mean?
(2) Here is the adjacency matrix for a graph:
[0 0 1 0 1]
[0 0 1 1 0]
[1 1 0 1 0]
[0 1 1 0 1]
[1 0 0 1 0]
The nodes in the graph are a,b,c,d, and e and this is the ordering of the rows and columns. (The first row and first column are for a, the second ones are for b, and so on.) What is the degree of each node, and how did you tell?
(3) Here is an adjacency matrix for another graph:
[0 0 1 0 1]
[1 1 0 1 0]
[0 0 1 1 0]
[1 0 0 1 0]
[0 1 1 0 1]
Is this second graph isomorphic to the one in exercise 2? Why or why not? (Remember you don't have to be right here, and we don't care yet about formality, so just give your best thought about it.)