Graph Theory Basics [eng|esp]

Racso
3,459 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content
Previous: Basics

We already know what graphs are. Now, let's see how can we represent graphs in ways other than drawing. This will be useful if we want to work with graphs with a computer.

Adjacency List

Remember our cities graph?

Graph example

Let's make a list of each node's neighbors:

  • CAR: MED, BUC
  • MED: CAR, BUC, BUE, ARM, BOG
  • BUC: CAR, MED, BOG, YOP
  • BUE: MED, CAL, PAS
  • ARM: MED, BOG, CAL
  • BOG: MED, BUC, YOP, ARM, CAL
  • YOP: BUC, ARM, BOG, LET
  • CAL: BUE, ARM, BOG, YOP, LET, PAS
  • PAS: BUE, CAL
  • LET: CAL, YOP

That's the adjacency list of the graph: a list of lists describing the neighbors of each node.

If the graph is directed, a node B only appears in the list of a node A if there's an edge from A to B. For example, in our directed Twitter graph:

Directed graph example

  • A: B, C
  • B: A
  • C: B

Adjacency Matrix

Graphs can also be represented with adjacency matrices. Here's the adjacency matrix of our cities graph:

CARBUCYOPBOGLETCALARMMEDBUEPAS
CAR0100000100
BUC1011000100
YOP0101111000
BOG0110011100
LET0010010000
CAL0011101011
ARM0011010100
MED1101001010
BUE0000010101
PAS0000010010

Adjacency matrices have the graph nodes in both their rows and columns. The value on each cell shows if there exists an edge between the pair of nodes of the corresponding row and column. For example, the cell in row BOG and column BUC has a value of 1 because there is an edge between BOG and BUC, whereas the cell in row PAS and column YOP has a 0 because there's no edge between those two nodes.

A graph may have several adjacency matrices. In the example above, if you put the nodes in a different order, you'll have a new adjacency matrix of the same graph.

As you can see, if a graph is undirected, its adjacency matrices are symmetrical. On the other hand, if the graph is directed, the matrices are not symmetrical, as a 1 only appears in a cell if there's an edge from the node of the row to the node of the column. For example, the following is the adjacency matrix of our Twitter graph:

ABC
A011
B100
C010

Exercise

The shown Python function is used for obtaining some information about a given graph. The graph is passed to the function as an adjacency list, and the function returns the maximum degree of a node of the graph, the amount of loops in the graph and a boolean indicating whether the graph has parallel edges or not.

Fix the function so it returns the desired information. You may assume that the graph will at most have 5 nodes, numbered from 1 to 5.

The shown function should return some information about a given graph. Fix it so it does it correctly.
1
2
3
4
5
def get_graph_info(adj_list):
#adj_list is the adjacency list of a graph. It's a list of lists, with each element being the two nodes connected by an edge.
#For example, if adj_list=[[0,1],[2,3],[4,3]], we have three edges, one connecting nodes 0 and 1, another one connecting nodes 2 and 3 and a third one connecting nodes 4 and 3.
return 2, 0, False #fix me: for the given graph, return: maximum grade of a node, number of loops, boolean representing if there are parallel edges.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Ending

Congratulations! Now you have some fundamentals about graph theory. Now, you may learn more concepts abouth graphs, or start to learn some useful algorithms to apply them. The choice is yours!

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content