Graph Theory

From ACSL Category Descriptions
Revision as of 13:19, 5 September 2018 by Marc Brown (Talk | contribs) (Video Resources)

Jump to: navigation, search

Many problems are naturally formulated in terms of points and connections between them. For example, a computer network has PCs connected by cables, an airline map has cities connected by routes, and a school has rooms connected by hallways. A graph is a mathematical object which models such situations.

Overview

A graph is a collection of vertices and edges. An edge is a connection between two vertices (or nodes). One can draw a graph by marking points for the vertices and drawing lines connecting them for the edges, but it must be borne in mind that the graph is defined independently of the representation. For example, the following two drawings represent the same graph:

Graph 1.png Graph 3.png

Terminology

The precise way to represent this graph is to identify its set of vertices {A, B, C, D, E, F, G, H, I, J, K, L, M}, and its set of edges between these vertices {AG, AB, AC, LM, JM, JL, JK, ED, FD, HI, FE, AF, GE}.

A path from vertex x to y in a graph is a list of vertices, in which successive vertices are connected by edges in the graph. For example, BAFEG is path from B to G in the graph above. A simple path is a path with no vertex repeated. For example, BAFEGAC is not a simple path.

A graph is connected if there is a path from every vertex to every other vertex in the graph. Intuitively, if the vertices were physical objects and the edges were strings connecting them, a connected graph would stay in one piece if picked up by any vertex. A graph which is not connected is made up of connected components. For example, the graph above has three connected components: {I, H}, {J, K, L, M} and {A, B, C, D, E, F, G}.

A cycle is a path, which is simple except that the first and last vertex are the same (a path from a point back to itself). For example, the path AFEGA is a cycle in our example. Vertices must be listed in the order that they are traveled to make the path; any of the vertices may be listed first. Thus, FEGAF and GAFEG are different ways to identify the same cycle. For clarity, we list the start / end vertex twice: once at the start of the cycle and once at the end.

We’ll denote the number of vertices in a given graph by V, the number of edges by E. Note that E can range anywhere from V to V2 (or 1/2 V(V-1) in an undirected graph). Graphs will all edges present are called complete graphs; graphs with relatively few edges present (say less than V log(V)) are called sparse; graphs with relatively few edges missing are called dense.

Trees

A graph with no cycles is called a tree. There is only one path between any two nodes in a tree. A tree on N vertices contains exactly N-1 edges. A spanning tree of a graph is a subgraph that contains all the vertices and forms a tree. A group of disconnected trees is called a forest.

Directed graphs are graphs which have a direction associated with each edge. An edge xy in a directed graph can be used in a path that goes from x to y but not necessarily from y to x. For example, a directed graph similar to our example graph is drawn below:

Graph 4.png

There is only one directed path from D to F. Note that there are two edges between H and I, one each direction, which essentially makes an undirected edge. An undirected graph can be thought of as a directed graph with all edges occurring in pairs in this way. A dag (directed acyclic graph) is a directed graph with no cycles.

Adjacency Matrices

It is frequently convenient to represent a graph by a matrix, as shown in the second sample problem below. If we consider vertex A as 1, B as 2, etc., then a “one” in M at row i and column j indicates that there is a path from vertex i to j. If we raise M to the pth power, the resulting matrix indicates which paths of length p exist in the graph. In fact, the quantity Mp(i,j) is the number of paths.

Traversability

There are many applications of graphs and associated algorithms that will not be included in this topic except for the Elementary Division. A Hamiltonian circuit is finding a path by which every vertex can be visited once and only once. An Euler circuit is finding a path by which every edge can be used once and only once. Graphs are traversable if there exists an Euler circuit unlike the famous Seven Bridges of Königsberg:

Konigsberg.png

Rules of traversability show that vertices can be either odd or even based on how many edges are incident on it. A graph is traversable if there are 0 or 2 odd vertices. If there are 2 odd vertices, then the path must begin with one of them and end with the other. With no odd edges, the path can begin with any vertex in the graph. Conflict theory and proof of the Four Color Theorem also use principles of graph theory.

Sample Problems

Sample Problem 1

Find the number of different cycles contained in the directed graph with vertices {A, B, C, D, E} and edges {AB, BA, BC, CD, DC, DB, DE}.

Solution: The graph is as follows:

Graph s1.png

By inspection, the cycles are: {A,B}, {B,C,D} and {C,D}. Thus, there are 3 cycles in the graph.

Sample Problem 2

Given the directed graph below, how many more paths of length 3 would exist if edges AE and EA were added?

Graph s1.png

Solution:

By using adjacency matrices, the current one is

Matrix1 s2.png

After adding edges AE and EA, the matrices are:

Matrix2 s2.png

There are 6 more paths of length 2 since 16 – 10 = 6.

Sample Problem 3

In the following directed graph, find the total number of different paths from vertex A to vertex C of length 2 or 4.

Graph s3.png

Solution:

Let matrix M represent the graph. Recall that the number of paths from vertex i to vertex j of length p equals M p[i,j]. The values of M, M 2 and M 4 are:

Matrix s3.png

There is 1 path of length 2 (M 2[1,3]) and 3 paths of length 4 (M 4[1,3]).

Sample Problem 4

Given the adjacency matrix, draw the directed graph.

Matrix s4.png

Solution:

The vertices do not have to be in those exact locations, but the edges must be the same.

Graph s4.png

Video Resources

The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.

https://youtu.be/vtTCRMGB0K8 Graph Theory ACSL Example Problem Tangerine Code A general tutorial on graph theory that can be used for American Computer Science League.

https://youtu.be/H96Lo2q_FSk ACSL - Graph Theory Worksheet 1 misterminich Draw the directed graph with vertices A, B, C, D, E and the directed edges AB, BC, AD, BC, DC, ED, and EA.

https://youtu.be/y1fdIb_oNG0 ACSL Graph Theory Worksheet 3 misterminich How many paths of length 2 are there in the directed graph show


Graph Theory (Intro)




https://youtu.be/44sQJK4BycY CS 106B Lecture: Graphs: basic concepts CS 106B, Spring 2015, Stanford University Videotape of a lecture at Stanford University

https://youtu.be/gXgEDyodOJU Data structures: Introduction to graphs mycodeschool FIrst or a two-part series, giving an overview of graphs.

https://youtu.be/AfYqN3fGapc Data structures: Properties of Graphs mycodeschool Second of a two-part series.