Graph Theory

Graph Theory

Graph Theory An Introduction Seven Bridges of Knigsberg Leonhard Euler in 1736 laid the foundations of graph theory. The city of Knigsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands

which were connected to each other and the mainland by seven bridges. He wished to devise a walk through the city that would cross each bridge once and only once. Sex in America On average, who has more opposite-gender partners, men or women? The University of Chicago interviewed a random sample of 2500

people over several years to try to get an answer to this question. Their study, published in 1994, and entitled The Social Organization of Sexuality found that on average men have 74% more opposite gender partners than women. ABC News Primetime Live found through a survey in 2004 that the average man has 20 partners, and women 6, over their lifetimes, with a claimed 2.5% margin of error. (Thats 233%) What do you think about this? (mathematically)

Introduction Informally, a graph is a bunch of dots connected by lines Formal graphs Formally, a graph is a pair of sets (V, E), where: V is a nonempty set whose elements are called vertices. E is a collection of two element subsets of V called edges. The vertices correspond to the circles in the picture, and the edges correspond to the lines. Thus, the dots and lines diagram above is a

pictorial representation of the graph (V, E) where: V = {A, B, C, D, E, F, G, H, I} E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F} , {E, G} , {H, I}} . Example Graph reprsentation The above graph is (V, E) where: V = {A, B, C, D, E, F, G, H, I} E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F} , {E, G} , {H, I}} .

Graph Definitions Graphs networks Vertices nodes Edges arcs Two vertices in a graph are said to be adjacent if they are joined by an edge, and an edge is said to be incident to the vertices it joins. The number of edges incident to a vertex is called the degree of the vertex. Deleting some vertices or edges from a graph leaves a subgraph. Formally,

a subgraph of G = (V, E) is a graph G = (V , E ) where V is a nonempty subset of V and E is a subset of E. Graph terms Find nodes that are adjacent. What node are incident of C? What is the degree of A, of F, of G? Define a valid proper subgraph of the graph above.

Graph variations In a multigraph, there may be more than one edge between a pair of vertices. Graph variations In a directed graph are arrows pointing to one endpoint or the other. Common Graphs

Complete Graph K6 Cycle with 5 vertices Empty Graph Path with 5 vertices

Sex in America Men have 74% more opposite gender partners than women? Let G = (V, E) be a graph where the set of vertices V consists of everyone in America. Let us partition V into MV (men) and WV (women):V (men) and WV (men) and WV (women):V (women): What d o the edges

represe nt? Sex in America In US |V| = 300 million, |M| = 147.6 million, |W| = 152.4.million. A LOT of possible edges! Sorry

guys! Let Am be average number of male OGPs*, and Aw is average female OGPs Does Am/Aw =1.74? ! So men are having 3% more OGP then

women, on average *OGP Opposite Gender Partnerships. Paths A path is a graph P = (V, E) of the form V = {v1, v2, . . . , vn}

E = {(v1 ,v2), (v2 ,v3), . . . ,(vn1 ,vn)} Similarly, a cycle is a graph C = (V, E) of the form: C = (V, E) of the form V = {v1, v2, . . . , vn} E = {(v1 ,v2), (v2 ,v3), . . . ,(vn1 ,vn), ( vn, v1) } Connectivity A graph is connected if for every pair of vertices u and v, the graph

contains a path with endpoints u and v as a subgraph. Not Connected two Connected components Connected one Connected

components A Simple Connectivity Theorem Theorem. Every graph G = (V, E) has at least |V | |E| connected components. Can you prove it? A Simple Connectivity Theorem Theorem. Every graph G = (V, E) has at least |V | |E| connected

components. Proof. We use induction on the number of edges. Let P(n) be the proposition that every graph G = (V, E) with |E| = n has at least | | V n connected components. Base case: In a graph with 0 edges, each vertex is itself a connected component, and so there are exactly |V | 0 = | | V connected components. A Simple Connectivity Theorem

Inductive step: Now we assume that the induction hypothesis holds for every n-edge graph in order to prove that it holds for every (n + 1)-edge graph, where n 0. Consider a graph G = (V, E) with n + 1 edges. Remove an arbitrary edge uv and call the resulting graph G . By the induction assumption, G has at least |V | n connected components. Now add back the edge uv to obtain the original graph G. If u and v were in the same connected component of G , then G has the same number of connected components as G , which is at least |V | n. Otherwise, if u and v were in different connected components of G , then

these two components are merged into one in G, but all other components remain. Therefore, G has at least |V| n 1 = | V | (n + 1) connected components. Distance and Diameter The distance between two vertices in a graph is the length of the shortest path between them. The diameter of a graph is the distance between the

two vertices that are farthest apart. Traversing a Graph Can you walk every hallway in the Ascension Hall exactly once? If we represent hallways and intersections with edges and vertices, then this reduces to a question about graphs. Euler Tours and Hamiltonian Cycles A walk in a graph G is an alternating sequence of vertices and edges of

the form: v0, v v1, v1, v1v2, v2, . . . , vn1, vn1vn, vn If v0 = vn, then the walk is closed. Walks are similar to paths. However, a walk can cross itself, traverse the same edge multiple times, etc. There is a walk between two vertices if and only if there is a path between the vertices. The entire field of graph theory began when Euler asked whether the seven bridges of Knigsberg could all be traversed exactly once.

Euler Tours and Hamiltonian Cycles An Euler walk is a walk that contains every edge in a graph exactly once. Similarly, an Euler tour is an Euler walk that starts and finishes at the same vertex; that is, v0 = vn. Euler tour Theorem. A connected graph has an Euler tour if and only if every vertex has even degree.

Corollary. A connected graph has an Euler walk if and only if either 0 or 2 vertices have odd degree. Hamiltonian cycles A Hamiltonian cycle is walk that starts and ends at the same vertex and visits every vertex in a graph exactly once. Determining whether a given graph has a Hamiltonian cycle is NP complete.

Adjacency Matrices A graph can be represented by an adjacency matrix. If a graph has vertices v1, . . . , vn, then the adjacency matrix is n n. The entry in row i, column j is 1 if there is an edge vi vj and is 0 if there is no such edge. Why is the matrix symmetric? What about a directed graph?

What would it mean to have nonzero entries o n the diagonal? Trees A connected, acyclic graph is called a tree. A vertex of degree one is called a leaf Can we add or

remove an edge and still have a tree? Trees Theorem. Every tree T = (V, E) has the following properties: 1. There is a unique path between every pair of vertices. 2. Adding any edge creates a cycle. 3. Removing any edge disconnects the graph.

4. Every tree with at least two vertices has at least two leaves. 5. |V| =| E| + 1. Spanning Trees Every connected graph G = (V, E) contains a spanning tree T = (V, E ) as a subgraph Binary Tree A binary tree is a rooted tree in which every vertex has at most two

children. Ordered, binary tree In an ordered, binary tree, the children of a vertex v are distinguished. One is called the left child of v, and the other is called the right child. For example, if we regard the two binary trees below as unordered, then they are equivalent. However, if we regard these trees as ordered, then they are different.

Problems 1. Prove that the sum of the degrees of the vertices of any finite graph is even. 2. Show that every simple graph has two vertices of the same degree. 3. Show that if n people attend a party and some shake hands with others (but not with themselves), then at the end, there are at least two people who have shaken hands with the same number of people.

4. Prove that a complete graph with n vertices contains n(n 1)/2 edges. Even degrees Prove that the sum of the degrees of the vertices of any finite graph is even. Proof: Each edge ends at two vertices. If we begin with just the vertices and no edges, every vertex has degree zero, so the sum of those degrees is zero, an even number. Now add edges one at a time, each of which

connects one vertex to another, or connects a vertex to itself (if you allow that). Either the degree of two vertices is increased by one (for a total of two) or one vertexs degree is increased by two. In either case, the sum of the degrees is increased by two, so the sum remains even. Two vertices of the same degree Show that every simple graph has two vertices of the same degree. Proof: This can be shown using the pigeon hole principle. Assume that the graph has n vertices. Each of those vertices is connected to either 0,

1, 2, . . . , n 1 other vertices. If any of the vertices is connected to n 1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus it is impossible to have a graph with n vertices where one is vertex has degree 0 and another has degree n 1. Thus the vertices can have at most n 1 different degrees, but since there are n vertices, at least two must have the same degree. Hand Shaking Show that if n people attend a party and some shake hands with

others (but not with themselves), then at the end, there are at least tw Proof: See previous problem. Each person is a vertex, and a handshake with another person is an edge to that person. o people who have shaken hands with the same number of people. Complete Graph Prove that a complete graph with n vertices contains n(n 1)/2 edges. Proof: This is easy to prove by induction. If n = 1, zero edges are

required, and 1(1 0)/2 = 0. Assume that a complete graph with k vertices has k(k 1)/2. When we add the (k + 1)st vertex, we need to connect it to the k original vertices, requiring k additional edges. We will then have k(k 1)/2 + k = (k + 1)((k + 1) 1)/2 vertices, and we are done.

Recently Viewed Presentations

  • Affordable housing background Michigan PSC Low-Income Energy Work

    Affordable housing background Michigan PSC Low-Income Energy Work

    Combined rebate value of $98,000. 53,079 kWh savings. Big Rapids Housing Commission "On average, residents' energy bills declined 24 percent in comparison to a year ago," said Laurie H., Assistant Director "One tenant said she saw her bill go down...
  • Diapositive 1 - imagiLEOnation

    Diapositive 1 - imagiLEOnation

    L'île devint l'île du Mont Royal puis Montréal. La montagne possède trois sommets ou collines : la Grosse Montagne ou colline Mont-Royal, l'Outremont car il fallait passer la première pour y arriver, jadis appelée Pain de Sucre sous le régime...
  • ISYS 512/812 Business Application Design and Development

    ISYS 512/812 Business Application Design and Development

    ISYS 350 Building Business Applications David Chao Business Applications 1. Database-centric applications Examples: Login to a website Join a website to become a member Online shopping Business Applications 2.
  • CMR Guidelines

    CMR Guidelines

    Before we begin, it is important that you refer to the Fund's Consultant Payment Bulletin if the bulletin was referenced in your contract. The following presentation will provide step-by-step instruction on how to submit an application for payment of design...
  • ANTHONY INDEPENDENT SCHOOL DISTRICT Maintenance and ...

    ANTHONY INDEPENDENT SCHOOL DISTRICT Maintenance and ...

    ANTHONY INDEPENDENT SCHOOL DISTRICT Erica Saldivar, Director Maintenance and Operations Department 620 Sixth Street, Anthony Texas, 79821-1279 Phone: (915) 886-6516 Fax: (915) 886-2420
  • Evidence that Demands a Verdict! Investigating the Case

    Evidence that Demands a Verdict! Investigating the Case

    He put his skills to work in order to "Save" Leslie from "Christianity" by exposing it as religious imagination or manipulation. What began as a serious and sincere "case against Christ" led Lee down the pathway of objective "facts" that...
  • Fibrous proteins - prime.edu.pk

    Fibrous proteins - prime.edu.pk

    Elastic fibers are composed of elastin and glycoproteinmicrofibrils and are found in the lungs, the walls of large arteries, and elastic ligaments. They can be stretched to several times their normal length, but recoil to their original shape when the...
  • 21 Annual st In conjunction with Earth Day

    21 Annual st In conjunction with Earth Day

    Ed Stone Park had 210 volunteers and collected 2100 lbs of garbage. If anyone knows who this watch belongs to please contact Environmental Management at 386-736-5927. Rescued by a volunteer, a baby possum.