Intro to Graphs

 You may have heard of a “graph” as a pie chart (a budget?), a line graph (change of something over time?), a histogram (into which buckets do values fall?), or another type. In computer science and related fields of math (this time, not statistics), a “graph” doesn’t mean those tools for representing data, but instead means, roughly, “a set of dots connected by lines.”

A “dot” is called a node or a vertex, and a “line” is called an “edge.” The following is a very simple graph, with 3 nodes and 3 edges.


And this is another graph with 5 nodes and 10 edges.

These are both “connected” graphs, because they don’t have any parts floating around in empty space, without any edges connecting the stray vertices to the rest. More formally, there is only one “component” in each of these graphs, a region of the graph connected by vertices and edges.

So much of computer science revolves around abstract objects like these graphs, so let’s look at a few special graphs.

K-graphs are called “complete” and identified by their number of vertices. You’ve already seen K5 and K3. Complete graphs have some number of vertices, and every possible edge between them. The binomial coefficient, using as inputs n and 2, gives the number of possible pairs of nodes to be connected by edges, which is the number of edges in a K.

Cycles are graphs that form a closed loop. Like K-graphs, C-graphs (be careful: complete is K, and cycle is C) are identified by the number of vertices they have, which is also the number of edges. Think about what C7, or C32678 would look like.

So far, all the graphs we’ve seen have been undirected—that is, there is no restriction on which way you move through a graph like there would be in a road network with some one-way streets, allowing movement only in that direction.

Every graph so far—every K and every C—has, deliberately or not, been cyclic. That is, each one had contained a cycle. Take a minute to draw out, on a whiteboard or on paper, a graph that does not have any cycles.

There is another category of graph called a bipartite graph. These graphs (from “bipartite” = “two parts”) are defined with two numbers, not just one. There is some group of vertices on the left, and another group on the right. A complete bipartite graph, known as K(L,R), connects all the left vertices with all the right ones, but has no left-left or right-right connections. The classic example, K(3,3) is often framed as the following:

• Alice has a house
• She needs water
• She needs heat
• She needs electricity
• Bob has a house
• He needs water
• He needs gas
• He needs electricity
• Charlie has a house
• He needs water
• He needs gas
• He needs electricity

Alice, Bob, and Charlie all need to connect to the water supply, get natural gas, and hook up to the meter. But Alice won’t take Charlie’s gas, just like Bob won’t take Alice’s water, and so on.

 

K(3,3) looks like this:

 

People sometimes call a graph where there’s one central node and all other nodes connect to it, and only to it, a “star(fish)” graph.

In many problems, the “degree” of a vertex, and, in directed graphs, this usually split by direction, in versus out. The “degree” of a vertex is the number of edges that come in, go out, or both (depending on if you want to know “degree,” “in-degree,” or “out-degree).

There are two common problems which we’ll cover in future articles, but I’ll introduce them now, and then, in the future, link to the articles working through a solution:

• Does a graph have an Eulerian cycle (or equivalently, “Is the graph Eulerian?”)—does there exist a cycle through the graph using every edge exactly once
• Does the graph have a Hamiltonian path (or equivalently, “Is the graph Hamiltonian?”)—does there exist a path through the graph that consumes every vertex exactly once?

Try to answer these two questions, but be warned—start with very small graphs, no bigger than any of the ones I’ve given as examples here. For now, suffice it to say in plain English that these problems are known to be “very hard.” In future articles coming up very soon, we’ll put some mathematical rigor into how we can classify problems and solutions.

Finally, let’s single out a particular class of graph: one which has no cycles or directed edges (and thus has exactly one path between any pair of nodes; try to prove this yourself), and exists in only a single component. They are called “trees” (they actually look like trees’ root systems, rather than what you see above ground), and they’re some of the most important graphs in computer science. We will devote many future articles to trees.