Main content

## Computer science

### Unit 1: Lesson 10

Graph representation# Describing graphs

Here's one way to represent a social network:

A line between the names of two people means that they know each other. If there's no line between two names, then the people do not know each other. The relationship "know each other" goes both ways; for example, because Audrey knows Gayle, that means Gayle knows Audrey.

This social network is a

**graph**. The names are the**vertices**of the graph. (If you're talking about just one of the vertices, it's a**vertex**.) Each line is an**edge**, connecting two vertices. We denote an edge connecting vertices u and v by the pair left parenthesis, u, comma, v, right parenthesis. Because the "know each other" relationship goes both ways, this graph is**undirected**. An undirected edge left parenthesis, u, comma, v, right parenthesis is the same as left parenthesis, v, comma, u, right parenthesis. Later, we'll see**directed graphs**, in which relationships between vertices don't necessarily go both ways. In an undirected graph, an edge between two vertices, such as the edge between Audrey and Gayle, is**incident**on the two vertices, and we say that the vertices connected by an edge are**adjacent**or**neighbors**. The number of edges incident on a vertex is the**degree**of the vertex.Audrey and Frank do not know each other. Suppose that Frank wanted to be introduced to Audrey. How could he get an introduction? Well, he knows Emily, who knows Bill, who knows Audrey. We say that there is a

**path**of three edges between Frank and Audrey. In fact, that is the most direct way for Frank to meet Audrey; there is no path between them with fewer than three edges. We call a path between two vertices with the fewest edges a**shortest path**. We've highlighted that particular shortest path below:When a path goes from a particular vertex back to itself, that's a

**cycle**. The social network contains many cycles; one of them goes from Audrey to Bill to Emily to Jeff to Harry to Ilana and back to Audrey. There's a shorter cycle containing Audrey, shown below: Audrey to Bill to Gayle and back to Audrey. What other cycles can you find?Sometimes we put numeric values on the edges. For example, in the social network, we might use values to indicate how well two people know each other. To bring in another example, let's represent a road map as a graph. Assuming that there are no one-way streets, a road map is also an undirected graph, with cities as vertices, roads as edges, and the values on edges indicating the distance of each road. For example, here's a road map, not to scale, of some of the interstate highways in the northeastern U.S., with distances next to edges:

The general term we use for a number that we put on an edge is its

**weight**, and a graph whose edges have weights is a**weighted graph**. In the case of a road map, if you want to find the shortest route between two locations, you're looking for a path between two vertices with the minimum sum of edge weights over all paths between the two vertices. As with unweighted graphs, we call such a path a**shortest path**. For example, the shortest path in this graph from New York to Concord goes from New York to New Haven to Hartford to Sturbridge to Weston to Reading to Concord, totaling 289 miles.The relationship between vertices does not always go both ways. In a road map, for example, there could be one-way streets. Or here's a graph showing the order in which a goalie in ice hockey could get dressed:

Now edges, shown with arrows, are

**directed**, and we have a**directed graph**. Here, the directions show which pieces of equipment must be put on before other pieces. For example, the edge from chest pad to sweater indicates that the chest pad must be put on before the sweater. The numbers next to the vertices show one of the many possible orders in which to put on the equipment, so that undershorts go on first, then socks, then compression shorts, and so on, with the blocker going on last. You might have noticed that this particular directed graph has no cycles; we call such a graph a**directed acyclic graph**, or**dag**. Of course, we can have**weighted directed graphs**, such as road maps with one-way streets and road distances.We use different terminology with directed edges. We say that a directed edge

**leaves**one vertex and**enters**another. For example, one directed edge leaves the vertex for chest pad and enters the vertex for sweater. If a directed edge leaves vertex u and enters vertex v, we denote it by left parenthesis, u, comma, v, right parenthesis, and the order of the vertices in the pair matters. The number of edges leaving a vertex is its**out-degree**, and the number of edges entering is the**in-degree**.As you might imagine, graphs—both directed and undirected—have many applications for modeling relationships in the real world.

### Graph sizes

When we work with graphs, it's helpful to be able to talk about the set of vertices and the set of edges. We usually denote the vertex set by V and the edge set by E. When we represent a graph or run an algorithm on a graph, we often want to use the sizes of the vertex and edge sets in asymptotic notation. For example, suppose that we want to talk about a running time that is linear in the number of vertices. Strictly speaking, we should say that it's \Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis, using the notation vertical bar, dot, vertical bar to denote the size of a set. But using this set-size notation in asymptotic notation is cumbersome, and so we adopt the convention that in asymptotic notation, and

*only*in asymptotic notation, we drop the set-size notation with the understanding that we're talking about set sizes. So, instead of writing \Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis, we write just \Theta, left parenthesis, V, right parenthesis. Similarly, instead of \Theta, left parenthesis, \lg, vertical bar, E, vertical bar, right parenthesis, we write \Theta, left parenthesis, \lg, E, right parenthesis.This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

- What do graphs have to do with algorithms?(32 votes)
- A large number of problems can be converted into graph problems.

If we have algorithms for solving graph problems, we can also solve the problems that we can convert into graph problems.

For example:

We can convert the 15 puzzle game (http://en.wikipedia.org/wiki/15_puzzle) into a graph problem.

We can then use a graph traversal algorithm (A* would typically be used) to solve the puzzle.

So, we can use a graph based algorithms to solve a problem, that at first glance, didn't look like a graph problem.(55 votes)

- When the article said that edges are incident on vertices, it made me think of a lines and points. Then I realized that you need two points to describe a line, but you can have as many as you like. Can edges work the same way, with more than two vertices per edge? If so, perhaps there could be a Khan Academy video or article on how that works and what it's used for?(7 votes)
- In geometry, lines are of a continuous nature (we can find an infinite number of points on a line), whereas in graph theory edges are discrete (it either exists, or it does not).

In graph theory, edges, by definition, join two vertices (no more than two, no less than two).

Suppose that we had some entity called a 3-edge that connects three vertices.

Suppose that we had a 3-edge connecting vertices A,B,C.

I would suggest that we could simply replace the 3-edge with 3 regular edges:

-an edge connecting A,B

-an edge connecting A,C

-an edge connecting B,C

We could do something similar with any n-edge that connects n vertices. As such, we typically just stick to using regular edges (we have many good algorithms that use regular edges).

Hope this makes sense(21 votes)

- It'd be very helpful if you could make videos for Euclidean and Hamiltalion graphs!(9 votes)
- What is a Bipartite graph?(4 votes)
- A graph where the vertices can be split into two sets A and B and every edge in the graph connects a vertex in A to a vertex in B.

bi - for the**two**sets

partite - for the**partitioning**(splitting) of vertices into those two sets(7 votes)

- What's so cumbersome about writing the absolute value denotation?(3 votes)
- Nothing it's just extraneous, like writing out all the H's s organic chemistry. Like Einstein said everything should be made as simple as possible, but not simpler.(5 votes)

- For the hockey example, the player could, for example, do undershorts, t-shirt, socks, then compression shorts, and there are other similar examples where there aren't dependencies. Why aren't these edges in the graph?(2 votes)
- Underpant, Sock, T-shirt can be worn in any order. Hence no edge between then. Here the edge denoted dependency.(1 vote)

- what is the use of graphs(1 vote)
- Why is running time of V, (assymptotic)O(V) but that of E is (assymptotic)O(lgE)?(0 votes)
- It's just an example you can certainly have O(E) algorithms and O(log V) algorithms(4 votes)

- How does Graph theory is used in general(1 vote)
- Graphs are used to express relationships between objects. The objects are nodes, and the edges are the relationships. The edges can be given weight to express something about the relationship.

I'll only mention two major applications that are seen in computer science, but there are many more.

One example is using the nodes as destinations, the edges as paths between destinations, and the weights on the edges as distances between those destinations. From there we can using algorithms to find:

- a possible route between two destinations,

- the shortest path between destinations,

- the smallest distance required to connect all destinations

Another example is using the nodes as destinations, the edges as pipes, with the weights as capacity of those pipes. We can use an algorithm to:

-figure out the maximum flow from one destination to another

Many problems can be solved by converting them into problems that look like these.(1 vote)

- can you define an algorithm for finding in-degree and out-degree of each and every node of a graph ?(1 vote)