• There is a lot more to graphs than that.

• \(V\) is the vertex set. Also called nodes.
• \(E\) is the set of edges. Each edge connects two vertices.

• So \(a\) is either connected to \(b\) or it isn't.

• The text usually draws something like the first.
• I'll usually draw something like the last.
• The arrangement of nodes/edges doesn't matter when we draw it. This is also the same graph:

• In a digraph, the direction of the edge matters.
• Vertices can be connected in one direction but not the other.
• Digraphs are usually drawn with arrows on the edges to indicate their direction:

• In this graph, there is an edge from \(a\) to \(b\), but no edge from \(b\) to \(a\).

• They are drawn just about how you'd expect:

• Graphs without multiple edges are simple graphs.

• Multigraphs are rarely used.
• We'll say “digraph” when direction matters.

• We can make each element of the set a node, and each element of the relation an edge.
• For example, the greater-than-or-equal relationship on a few values:

• A symmetric relation can be represented using an undirected graph.
• For example, the relation \(a\equiv b\text{ (mod }3\text{)}\) for a few values:

• Note: there's no requirement that the vertices be connected to one another: the above figure is a single graph with 11 vertices.
• Edges that start and end at the same vertex are called loops.

• Much like with relations: we can think of some other problem as a graph, and then apply any graph theorems to help us understand it.
• … or graph algorithms to analyze them.

• Let \(V\) be the set of all users.
• Let \(E\) be the users who are friends.
• This is an undirected graph (in every social network I can think of).
• It's also probably large. For Facebook, \(|V|\approx 1.1\times 10^{9}\) and \(|E|\approx 1.5\times 10^{11}\).
• Obviously if we're going to do any analysis on a graph that large, we have to pay close attention to the big-O of the algorithm.

• We can have a vertex for each atom, and an edge for each bond.

• The vertices will be the intersections where roads meet.
• The edges will be the roads.
• Directed graph (so we can represent one-way roads), but most edges will have an opposite-direction partner.
• We could even label edges with their distance, or number of cars that use them, or whatever other data we need.
• Then, we can ask questions like “what is the shortest way to get from A to B”

• We can think of a maze like this as a graph:

  

  Source: mazegenerator.net

• Find any “important” points in the maze and call them nodes; connect nodes with edges when they are connected in the graph:

• Now we have a graph that captures everything important about the maze:

• And we can ask how about a path from \(a\) to \(k\) in that graph.
• … or the shortest path, or the path that visits the most places on its way, or…
• We didn't really have to select only “important” points as our vertices.
• We could have made every grid location a vertex, and joined them as appropriate.
• That would have created a much bigger graph (64 nodes, many with degree 2), but still captured everything about the maze.
• Maybe that graph would have been better: getting the shortest path would have been more meaningful.

• We can take the computer to be nodes, and connections between then to be edges.
• Undirected graph: every networking technology is bidirectional.
• Maybe a multigraph if we want to represent that computers might have multiple redundant connections between them.
• But usually a simple graph: put an edge if the computer are connected in any way.
• Again, we can then ask questions about how to route information between two computers, or how many paths there are between computers, or what connections could fail without losing connectivity, or….

• An edge connects the nodes at either end.
• The number of edges at a node is the nodes degree.
• Where we need to, we'll write \(\operatorname{deg}(v)\) for the degree of vertex \(v\).

• … since each edge has two ends.
• Corollary: the number of vertices with odd degree must be even.

• An edge from \(u\) to \(v\) has \(u\) as its initial vertex and \(v\) as its end vertex.
• We have to count degree separately.
• The count of edges with \(v\) as the initial vertex is its out degree, \(\operatorname{deg}^{-}(v)\).
• The count of edges with \(v\) as the end vertex is its in degree, \(\operatorname{deg}^{+}(v)\).
• Then, \(|E|=\sum_{v\in V} \operatorname{deg}^{-}(v)=\sum_{v\in V} \operatorname{deg}^{+}(v)\).

• That is, every vertex is adjacent to every other.
• These are called \(K_n\).
• Here are \(K_3\), \(K_4\), \(K_6\), \(K_8\):

• \(K_n\) would represent the relation \(\{(a,b)\mid a\ne b\}\).
• The graph that models an equivalence relation is a collection of complete graphs (plus loops on each vertex): one for each equivalence class.

• They are called \(C_n\).
• These are \(C_3\), and \(C_6\).

• The vertices will be every possible \(n\) bit value.
• There will be an edge between two vertices when they differ by exactly one bit.
• So, 1101 will be connected to 1100, but not 1000 or 1101.
• These are \(Q_1\), \(Q_2\), \(Q_3\), and \(Q_4\):

• We can also define cubes recursively. \(Q_0\) is a single node with no edges.
• To create \(Q_{n+1}\), we make two copies of \(Q_{n}\) and join their corresponding edges.

• There are \(2^n\) nodes.
• They have relatively few edges: each vertex has degree \(n\).
• There is a path between any two nodes with at most \(n\) steps. It's easy to figure out what that path is.
• That's nice for a situation like connected processors: they can communicate effectively without requiring too much communications overhead.

• For example in the graph, we can take \(\{a,b,c\},\{d,e,f\}\) as a partition of the vertices:

• There are no edges between nodes in \(\{a,b,c\}\) or \(\{d,e,f\}\) so it is bipartite.
• We will usually draw bipartite graphs like that: with the partitions on the left/right and all edges sort-of-horizontal between the two.
• … or partitions on the top/bottom and the edges mostly-vertical.
• Of course, we don't have to draw the graph like that for it to be bipartite. This is the same graph drawn two different ways, and it's still bipartite.

• Are the cycles \(C_n\) bipartite? The cubes \(Q_n\)?
• At least we can answer for the complete graphs \(K_n\). Only \(K_2\) is. The rest have too many edges.

• One way to do that is to colour the vertices with two colours so no identically-coloured vertices share an edge:

• For example, here are \(K_{2,3}\) and \(K_{3,5}\):

• Remember that we don't have to draw them that way. This is also \(K_{3,5}\):

• … assuming the two sets are disjoint.
• For example, a relation from letters to words, where a letter is related to a word if it is in the word.

• For example, for this graph,

• Here are two subgraphs:

• For example, here is the union of the two graphs above:

• This is also a subgraph of the original above.

Theorem: A graph is bipartite if and only if it does not contain an odd-length cycle as a subgraph.

Proof: [Only if: odd cycle implies not bipartite.] Suppose we have a graph that contains an odd cycle. Let \(v_1,v_2,\ldots,v_n\) be the vertices in the cycle, with \(n\) odd. We can try to form two partitions \(A,B\) of the vertices.

Without loss of generality, we put \(v_1\) in \(A\). Then \(v_2\) must be in \(B\) since \(v_1\) and \(v_2\) are adjacent. Similarly, \(v_3\) must be in \(A\). We will have all odd-numbered vertices in \(A\) and even-numbered in \(B\).

Then \(v_n\) is in \(A\). Since there is an edge from \(v_1\) to \(v_n\), we cannot construct a partition to satisfy the definition of a bipartite graph.

[If: no odd cycles implies bipartite.] We can form a partition \(A,B\) as follows. Start with any vertex \(a\) and put it in partition \(A\). For each other vertex \(v\), look at the length \(n\) of the shortest path from \(a\) to \(v\) in the graph. If \(n\) is even, put \(v\) in \(B\); if it is odd, put it in \(A\).

Suppose we have two vertices \(v_1\) and \(v_2\) that are adjacent but in the same partition. Then the path from \(v_2\) to \(a\), plus the path from \(a\) to \(v_1\), plus the edge \((v_1,v_2)\) forms an odd-length cycle, and we have a contradiction.∎

• If we can come up with some algorithm to find odd cycles, we can use it to check if a graph is bipartite.

• … in a way we can write algorithms on them.
• The “right” way is going to depend on the graph and the algorithm we want to use.

• For each vertex, keep a list of vertices that are adjacent to it.
• For example, if we have this graph:

• The adjacency list is just:

  \(a\):	\(\{b,c,e\}\)
  \(b\):	\(\{a,b\}\)
  \(c\):	\(\{a,d,e\}\)
  \(d\):	\(\{c,e\}\)
  \(e\):	\(\{a,c,d\}\)

• For a directed graph, we can obviously just list the outgoing vertices.
• … or incoming vertices if that's more useful to the application at hand.
• The storage required for the adjacency list is going to be \(\Theta(|V|+|E|)\).

• For the graph above, \[\left[\begin{matrix}0&1&1&0&1 \\ 1&1&0&0&0 \\ 1&0&0&1&1 \\ 0&0&1&0&1 \\ 1&0&1&1&0 \\ \end{matrix}\right]\]
• For an undirected graph, the matrix will always be symmetric.
• For a (non-symmetric) directed graph, it won't be.
  \[\left[\begin{matrix}0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \\ 1&0&0&0 \\ \end{matrix}\right]\]
• We could allow numbers other than 0 and 1 to represent a multigraph.
• The storage required for the adjacency matrix is going to be \(\Theta(|V|^2)\).

• Then \(f\) is called the isomorphism.
• An isomorphism that maps the first to the last graph above is \(f(a)=q\), \(f(b)=r\), \(f(c)=s\), \(f(d)=t\), \(f(e)=u\), \(f(f)=v\).

• Apparently, databases of chemicals are arranged by isomorphism of the molecule.

• Reflexive: identity function.
• Symmetric: inverse function.
• Transitive: function composition.

• Obviously, if \(|V_1|\ne|V_2|\) or \(|E_1|\ne|E_2|\), then they aren't isomorphic.
• If the vertices have different degrees, then they can't be isomorphic. (e.g. if \(G_1\) has two nodes with degree 4, but \(G_2\) has three, they won't be isomorphic.)

• We could come up with other easy-to-check properties that would be preserved by an isomorphism.
• e.g. “contains a 4-cycle” or “has adjacent vertices of degree \(m\) and \(n\)”.
• These are graph invariants.
• But we could always come up with some example like the above which has the right properties but is not isomorphic (or is as hard to compute as isomorphism).
• Properties like “has a node labelled \(a\)” are not invariants.

• Actually, coming up with an algorithm is easy:

  procedure find_isomorphism(V1, E1, V2, E2)
      if |V1| ≠ |V2| or |E1| ≠ |E2|: return false
      for every possible bijection from V1 to V2
          check to see if each edge in E1 maps onto an edge in E2 under that function
          if it does: return the function
      return false

• But that's not exactly a fast algorithm: there are \(|V|!\) possible functions and \(|E|\) work to check each one.
• So the running time is \(\Theta(|E|\cdot|V|!)\) worst case. That's pretty bad.

• [I think \(n\) there is \(|V|+|E|\), but can't find a source to confirm.]
• That's much better: \(O(2^{\sqrt{n\log n}})\) is smaller than \(O(2^n)\), but the \(O(n!)\) for my solution is bigger.
• But it's still exponential.

• Maybe we (or somebody else) could come up with a decent algorithm for certain kinds of graphs.
• e.g. graphs with no loops. That sounds easier.
• Maybe we could come up with an algorithm that has a good-enough average case for the kinds of graphs we actually care about.
• … even if the worst case is really bad for graphs we don't use very often in a particular application.