Example: marketing

Graph Theory - Gordon College

Graph TheoryMAT230 Discrete MathematicsFall 2019 MAT230 (Discrete Math) Graph TheoryFall 20191 / 72 Outline1 Definitions2 Theorems3 Representations of Graphs: Data Structures4 Traversal: Eulerian and Hamiltonian Graphs5 Graph Optimization6 Planarity and ColoringsMAT230 (Discrete Math) Graph TheoryFall 20192 / 72 DefinitionsDefinitionAgraphG= (V,E) consists of a setVofvertices(also callednodes)and a an edge connects to a vertex we say the edge isincidentto the vertexand say the vertex is anendpointof the an edge has only one endpoint then it is called aloop two or more edges have the same endpoints then they are (Discrete Math) Graph TheoryFall 20193 / 72 DefinitionsDefinitionTwo vertices that are joined by an edge are is a vertex that is connected to exactly one other vertexby a single a Graph is a sequence of alternating vertices and +1withn 0.

weighted graph, then T is a minimal spanning tree of G if it is a spanning tree and no other spanning tree of G has smaller total weight. MAT230 (Discrete Math) Graph Theory Fall 2019 8 / 72. De nitions De nition The complete graph on n nodes, denoted K n, is the simple graph with

Tags:

  Spanning, Minimal, Minimal spanning

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Graph Theory - Gordon College

1 Graph TheoryMAT230 Discrete MathematicsFall 2019 MAT230 (Discrete Math) Graph TheoryFall 20191 / 72 Outline1 Definitions2 Theorems3 Representations of Graphs: Data Structures4 Traversal: Eulerian and Hamiltonian Graphs5 Graph Optimization6 Planarity and ColoringsMAT230 (Discrete Math) Graph TheoryFall 20192 / 72 DefinitionsDefinitionAgraphG= (V,E) consists of a setVofvertices(also callednodes)and a an edge connects to a vertex we say the edge isincidentto the vertexand say the vertex is anendpointof the an edge has only one endpoint then it is called aloop two or more edges have the same endpoints then they are (Discrete Math) Graph TheoryFall 20193 / 72 DefinitionsDefinitionTwo vertices that are joined by an edge are is a vertex that is connected to exactly one other vertexby a single a Graph is a sequence of alternating vertices and +1withn 0.

2 Ifv1=vn+1then the walk the walk is the number of edges in the walk. A walk oflength zero is atrivial (Discrete Math) Graph TheoryFall 20194 / 72 DefinitionsDefinitionAtrailis a walk with no repeated edges. Apathis a walk with norepeated vertices. Acircuitis a closed trail and atrivial circuithas asingle vertex and no edges. A trail or circuit isEulerianif it uses everyedge in the a nontrivial circuit in which the only repeated vertex is thefirst/last graphis a Graph with no loop edges or multiple edges. Edges ina simple Graph may be specified by a set{vi,vj}of the two vertices thatthe edge makes adjacent. A Graph with more than one edge between apair of vertices is called amultigraphwhile a Graph with loop edges iscalled (Discrete Math) Graph TheoryFall 20195 / 72 DefinitionsDefinitionAdirected graphis a Graph in which the edges may only be traversed inone direction.

3 Edges in a simple directed Graph may be specified by anordered pair (vi,vj) of the two vertices that the edge connects. We saythatviisadjacent tovjandvjisadjacent a vertex is the number of edges incident to the vertex andis denoted deg(v).DefinitionIn a directed Graph , thein-degreeof a vertex is the number of edgesincident tothe vertex and theout-degreeof a vertex is the number ofedgesincident fromthe (Discrete Math) Graph TheoryFall 20196 / 72 DefinitionsDefinitionA Graph isconnectedif there is a walk between every pair of distinctvertices in the graphHis asubgraphof a graphGif all vertices and edges inHarealso componentofGis a connected subgraphHofGsuch thatno other connected subgraph Graph is calledEulerianif it contains an Eulerian (Discrete Math) Graph TheoryFall 20197 / 72 DefinitionsDefinitionAtreeis a connected, simple Graph that has no cycles.

4 Vertices ofdegree 1 in a tree are called theleavesof the a simple, connected Graph . The subgraphTis aspanning treeofGifTis a tree and every node inGis a node graphis a graphG= (V,E) along with a functionw:E Rthat associates a numerical weight to each edge. IfGis aweighted Graph , thenTis aminimal spanning tree ofGif it is aspanning tree and no other spanning tree ofGhas smaller total (Discrete Math) Graph TheoryFall 20198 / 72 DefinitionsDefinitionThecomplete graphonnnodes, denotedKn, is the simple Graph withnodes{1,..,n}and an edge between every pair of distinct Graph is calledbipartiteif its set of nodes can be partitioned into twodisjoint setsS1andS2so that every edge in the Graph has one endpoint inS1and one endpoint bipartite graphonn,mnodes, denotedKn,m, is the simplebipartite Graph with nodesS1={a1.}

5 ,an}andS2={b1,..,bm}andwith edges connecting each node inS1to every node (Discrete Math) Graph TheoryFall 20199 / 72 DefinitionsDefinitionSimple graphsGandHare calledisomorphicif there is a bijectionffromthe nodes ofGto the nodes ofHsuch that{v,w}is an edge inGif andonly if{f(v),f(w)}is an edge ofH. The functionfis called simple, connected Graph is calledplanarif there is a way to draw it on aplane so that no edges cross. Such a drawing is called anembeddingofthe Graph in the a planar graphGembedded in the plane, afaceof the Graph is aregion of the plane created by the drawing. The area of the plane outsidethe Graph is also a face, called the unbounded (Discrete Math) Graph TheoryFall 201910 / 72 TheoremsTheoremLetGbe a connected Graph .

6 ThenGis Eulerian if and only if every vertexinGhas even (Handshaking Lemma)In any Graph withnverticesviandmedgesn i=1deg(vi) = 2mCorollaryA connected non-Eulerian Graph has an Eulerian trail if and only if it hasexactly two vertices of odd degree. The trail begins and ends these (Discrete Math) Graph TheoryFall 201911 / 72 TheoremsTheoremIfTis a tree withnedges, thenThasn+ graphs that are isomorphic to one another must have1 The same number of same number of same number of nodes of any given same number of same number of cycles of any given (Discrete Math) Graph TheoryFall 201912 / 72 TheoremsTheorem (Kuratowski s Theorem)A graphGis nonplanar if and only if it contains a copy ofK3,3orK5asa (Euler s Formula for Planar Graphs)For any connected planar graphGembedded in the plane withVvertices,Eedges, andFfaces, it must be the case thatV+F=E+ (Discrete Math) Graph TheoryFall 201913 / 72 Graphs vs PlotsRecall that a Graph consists of two sets.

7 A set of vertices and a set we often represent graphs visually, we can distinguish between agraph and aplotin the following way: A Graph stores information andconnections between information while a plot provides a visualrepresentation of the information stored in a that graphs are important, we now examine how we can representgraphs using a computer and see how one computer package (Discrete Math) Graph TheoryFall 201914 / 72A Quick Matrix ReviewAmatrixis a rectangular array of numbers. A matrix withmrowsandncolumnssaid to be anm in the matrix are addressed by their row and column a matrixA, the entryaijis in theithrow andjthcolumn that we always list the row index say a matrixAissymmetricifaji= Symmetric 0 5 2 11 3 0 14 6 8 30 7 3 1 Symmetric 0 3 7 13 8 5 07 5 2 41 0 4 0 MAT230 (Discrete Math) Graph TheoryFall 201915 / 72 Adjacency MatricesLetGbe a Graph withnvertices.

8 We can use ann nmatrix to store thegraph. Letgij={1 if vertexiis adjacent to vertexj0 if vertexiis not adjacent to vertexjFor example, the Graph on the left has the adjacency matrix on the 0 1 0 01 0 0 10 0 0 10 1 1 0 Note: matrix is symmetricThe adjacency matrix for a directed Graph will not be symmetric unless thedirected Graph itself is (Discrete Math) Graph TheoryFall 201916 / 72 Sparse Graphs and MatricesConsiderK30, the complete Graph with 30 vertices. This Graph hasC(30,2) = 435 edges since every vertex is connected to every other adjacency matrix will have 1 s in every non-diagonal position (why noton the diagonals?). We say the 30 30 adjacency matrix isdenseorfullsince most of the entries are considerC30, acycle(orring) Graph with 30 vertices.}

9 Each vertex isconnected to two other vertices to form a single ring or cycle. This meansthere are only 30 edges. So, while the adjacency matrix will be 30 30,only 60 entries in it will be non-zero. In this case we say the Graph and theadjacency matrix (Discrete Math) Graph TheoryFall 201917 / 72 Adjacency Matrix ExamplesAdjacency matrix forK88 8 matrix with 64 elements2 C(8,2) = 56 non-zero entries 0 1 1 1 1 1 1 11 0 1 1 1 1 1 11 1 0 1 1 1 1 11 1 1 0 1 1 1 11 1 1 1 0 1 1 11 1 1 1 1 0 1 11 1 1 1 1 1 0 11 1 1 1 1 1 1 0 Adjacency matrix forC88 8 matrix with 64 elements8 non-zero entries 0 1 0 0 0 0 0 11 0 1 0 0 0 0 00 1 0 1 0 0 0 00 0 1 0 1 0 0 00 0 0 1 0 1 0 00 0 0 0 1 0 1 00 0 0 0 0 1 0 11 0 0 0 0 0 1 0 MAT230 (Discrete Math)

10 Graph TheoryFall 201918 / 72 Edge ListsNote that in the case of undirected graphs we really only need theupper-right triangle or the lower-left triangle (about half) of the adjacencymatrix to store the information in the the case of directed graphs, we need the full either case, if the Graph is sparse, there are more efficient ways to storethe Graph . One of these is to maintain anedge (Discrete Math) Graph TheoryFall 201919 / 72 Edge Lists1 Edge List v1: For each vertex, store a list of vertices that the vertexis adjacent List v2: Store all edges in the Graph as a list of ordered Matrix 0 1 0 01 0 0 10 0 0 10 1 1 0 Edge List v1{{2},{1,4},{4},{2,3}}Edge List v2{(1,2),(2,1),(2,4),(3,4),(4,2),(4,3)}W hich version we choose to use is largely dependent on how we need toaccess the (Discrete Math) Graph TheoryFall 201920 / 72A walk around Gordon s campusIs it possible to start in front of the Ken Olsen Science Center (labeled E),walk along every pathway on Gordon s main campus exactly once, and endup back in front of the Science Center?


Related search queries