For each of the following graphs:
Show the concrete data structures if the graph was implemented via:
- adjacency matrix representation (assume a full V×V matrix)
- adjacency list representation (if non-directional, include both (v,w) and (w,v))
Answer:
Consider the following graph
The edges are labelled simply for convenience in describing graph properties.
-
How many edges does it have?
-
How many cycles are there in the graph?
-
How many cliques are there in the graph?
-
What is the degree of each vertex?
-
How many edges in the longest path from 5 to 8?
(without traversing any edge more than once)
Answer:
1. 11 edges (labelled a..k)
2. 6 cyles: 0-1-7-8-0, 1-2-7-1, 2-3-7-2, 0-1-2-7-8-0, 0-1-2-3-7-8-0, 1-2-3-7-1
3. 2 cliques: {1, 2, 7}, {2, 3, 7} (clique = complete subgraph with at least 3 nodes)
4. d(0) = 2, d(1) = 3, d(2) = 3, d(3) = 3, d(4) = 2, d(5) = 1, d(6) = 1, d(7) = 5, d(8) = 2
5. 7 edges, path is 5-4-3-2-7-1-0-8 or 5-4-3-7-2-1-0-8
Facebook could be considered as a giant "social graph"
- What are the vertices?
- What are the edges?
- Are edges directional?
- What does the degree of each vertex represent?
- What kind of graph algorithm could suggest potential friends?
Answer:
1. Vertices are people (Facebook users)
2. Edges are "friend" relationships
3. No - if you are someone's friend, they are also your friend
4. The degree of a vertex is the number of friends that the person represented by the vertex has
5. Breadth-first search - find your immediate friends, then consider their friends, and so on