[PDF] Lecture 17: Introduction to Graph Theory 1 Preliminaries PDF Lecture17.pdf

14 oct 2019 · written deg(v) is the number of non-self-loop edges adjacent to v plus two times the Graph Theory: Penn State Math 485 Lecture Notes [PDF]

Definition 1 3 The degree of a vertex v, written d(v), is the number of ends of edges which connect to that vertex

[PDF] Lecture Notes on Graph Theory

Lecture Notes on Graph Theory All graphs in these notes will be simple The sets of vertices and edges of a graph G will be denoted V (G) and E(G),

[PDF] Graph Theory Lecture Notes - Amazon AWS

Removing edges are in graph lecture handwritten notes Matrix and for the theory and results will do as a graph drawing the graph before, if no textbook for history

[PDF] Lecture Notes Graph Theory

6 déc 2016 · 2 Page 3 1 Introduction These brief notes include major definitions and theorems of the graph theory lecture held by Prof Maria Axenovich at

[PDF] Graph Theory Lecture Notes - Personal Psu - Penn State

20 juil 2011 · The lecture notes are loosely based on Gross and Yellen's Graph written deg(v ) is the number of non-self-loop edges adjacent to v plus two

[PDF] Notes on graph theory - Math User Home Pages

2 août 2016 · These are lecture notes on graph theory – the part of mathematics involved I have written the above proof in much detail, since it is the first

[PDF] Graph Theory Lecture Notes

The lecture notes are loosely based on Gross and Yellen's Graph Theory and It's written deg(v) is the number of non-self-loop edges adjacent to v plus two

[PDF] Notes on graph theory

13 déc 2010 · A simple cycle is a cycle that includes each vertex at most once Cycles are often written by giving their sequence of vertices v0v1v2 vkv0, where

[PDF] Lecture 17: Introduction to Graph Theory 1 Preliminaries

14 oct 2019 · written deg(v) is the number of non-self-loop edges adjacent to v plus two times the Graph Theory: Penn State Math 485 Lecture Notes [PDF]

Discrete Mathematics14-10-2019

Lecture 17: Introduction to Graph Theory

Instructor: Sourav Chakraborty Scribe: Subrat Prasad Panda1 Preliminaries Denition 1.1 (Graphs)A graph is a tupleG= (V;E)whereVis a (nite) set of ver- tices andEis a nite collection of edges.The set E contains elements from the union of the one and two element subsets of V . That is, each edge is either a one or two element subset of V .For instance, Figure 1.1 is a graph whereV=fv1,v2,v3,v4gand E=fe1,e2,e3,e4,e5,,e6g.[1]v 2v 4v 1v 3e 1e 2e 3e 4e 5e

6Figure 1.1: Example of a Graph.

Denition 1.2 (Simple Graphs)A simple graph is a nite undirected graph without loops and multiple edges.[2] Denition 1.3 (Degree)LetG= (V;E)be a graph and letv2V. The degree of v, written deg(v) is the number of non-self-loop edges adjacent to v plus two times the number of self-loops dened at v. More formally: deg(v) =j fe2E:9u2V(e=fu; vg)j+ 2j fe2E:e=fvgg j Here ifSis a set, thenjSjis the cardinality of that set.[1] Denition 1.4 (Path)ApathPin a graph is a sequence of vertices v1,v2,..., vksuch that v ivi+1is an edge for each i=1 ,..., k-1. The length of a pathPis the number of edges inP.[2] Denition 1.5 (Connected Graphs)A graphGisconnectedif any two vertices of the graph are joint by a path. If a graph G isdisconnected(i.e., not connected), then every maximal (with respect to inclusion) connected sub-graph of G is called a connected component of G.[2] 17-1 Denition 1.6 (Dense Graphs)A graphG= (V;E)is said to be dense if for every v2V,degree(v)>n2 , wheren=jVji.e number of edges is close to the maximal number of edges orjEj= (jVj2).[4] Denition 1.7 (Sparse Graphs)A graphG= (V;E)is said to be spare if for every v2V,degree(v)2 Representation of Graphs

2.1 Sets and Relation

Any graphsG= (V;E) can be represented in forms of Sets and Relation. For instance, the graph in Figure 1.1 can be represented as following:

2.2 Adjacency Matrix

Denition 2.1 (Adjacency Matrix)LetG= (V;E)be a graph and assume thatV= fv1;:::;vng. The adjacency matrix ofGis annnmatrix A dened as:[1] A ij=?1fvi;vjg 2E

0otherwise(2.1)

A ij=? v1v2::: vn v 1 v 2::: v n2 6

6640 1:::0

1 0:::1

0 0:::03

7 775?
nn Proposition 2.2The adjacency matrix of a simple graph is symmetric with diagonal en- tries as 0. Remark 2.3The adjacency matrix representation depends on explicit denition of entries, hence it's not unique. For instance, Using diagonal entries for dierent purposes(as diagonal entries are futile). Representation of zeroed entries with dierent integers or values. In case of simple undirected graph, the adjacency matrix is upper/lower triangular matrix. Hence, denition can be modied to optimize memory usages. 17-2

2.3 Adjacency List

Denition 2.4 (Adjacency List)LetG= (V;E)be a graph and assume thatV= fv1;:::;vng. The adjacency list of graphGis constructed by assigning a unique label from 0 ton1to each vertex and building an arrayAof length n where each entryA[i]contains a pointer to a linked list of all the out-neighbours of vertex i. Figure 2.1 shows the repre- sentation of adjacency list of a graph. In an undirected graph with edge u, v the edge will appear in the adjacency list for both u and v.0 1 2 n-1v 1v 2v 3v nv 4v 9v iv 2v 5v jv 3v k...... Figure 2.1: Representation of Graph with Adjacency List. Fact 2.5Searching for existence of an edge between any two vertices of a graph takesO(1) inadjacency matrixrepresentation, whereas it takesO(logn)(by the application of binary search) in case ofadjacency listrepresentation.

3 Euler's Handshaking Lemma

Theorem 3.1In any graphG= (V;E)where V and E represents vertices and edges then X v2Vdeg(v) =2 jEj(3.1) Proof.It can be proved using Adjacency Matrix. Let a graphG= (V;E) represented by Adjacency MatrixAijwhereVandEare the vertices and edges respectively. Then deg(vi) =n1X k=0A[i][k]. So,X v2Vdeg(vi) =n1X i=0n1X k=0A[i][k] = 2 jEjas each edge is rep- resented exactly twice by 1 in the matrixA[i][j], hence, summation of all the elements in matrixA[i][j] results in twice the number of vertices of graph.2 17-3

4 Properties of Adjacency Matrix

4.1 Square of Adjacency Matrix

Theorem 4.1LetA= (aij) =A(G)for some simple undirected graph G and deneS= (sij) =A2. Then for everyiandj,sijrepresents the number of two-walks (walks with two edges) from vertexvitovjinG.[5] A

2ij=j fkjAik= 1 =Akjg j(4.1)

Proof.Consider the entrysijinS. By denition,sij=nX k=1a ikakjand so one is contributed to the sum only whenaikandakjare 1. That is, when the edgesvivkandvkvjare inG, which corresponds to the two-walk, refer Figure 4.2, fromvitovjthroughvk.2v iv kv jv gFigure 4.1: Two walks fromvitovjthroughvk. Corollary 4.2The diagonal elementssiiofS=A2(whereAis the adjacency matrix) is equals to degree of(vi)i.e s ii=deg(vi)

4.2 Cube of Adjacency Matrix

Theorem 4.3Let A be the adjacency matrix of a simple undirected graph G and dene C ij=cij=A3. Then for every i and j,cijrepresents the number of dierent edge sequences of 3 edges between verticesviandvj. [6] A

3ij=j f(k;l)jAik= 1 =Akl=Aljg j(4.2)

Proof.Consider the entrycijin C. By denition,cij=nX k=1s ikakjwhich is equals tonX k=1( number of all dierent edges sequences of three edges from ith vertex to jth vertex via kth vertex). Refer Figure 4.2, summation produces the number of possible dierent edge sequences of three edges between ith and jth vertices.2 17-4 v iv kv jv lFigure 4.2: Three walks from vertexvitovjthroughvkandvl. Corollary 4.4The diagonals entriescii2A3denotes the number of triangular cycles passing through each vertexiin a simple graph. Corollary 4.5Trace ofA3is equals to 3 times the total number of triangular cycles in a simple graph.

4.3 Eigenvalue of Adjacency Matrix

Denition 4.6 (d-Regular Graph)A regular graph is a graph where every vertex has same degrees. A regular graph with vertices of degreedis called ad-Regular Graph. Figure 4.3 shows examples of 2-Regular Graphs. [7]v 1v 2v

3(a) 2-Regular Graph with 3 verticesv

1v 2v 3v

4(b) 2-Regular Graph with 4 vertices

Figure 4.3: Example of d-Regular Graphs

Denition 4.7 (Cut Set)Cut is a minimal set of edges, removal of which render the graph disconnected. The cut partitions a graph into two or more components making the graph disconnected. Set of edges fullling above properties forms cut set. Size of cut is dened by the fraction of edges in cut set with respect to cardinalityjEjof a graph G(V,E). For instance, 0:1 jEjis the cardinality of cut set which signies that the size of cut set is 0.1 times cardinality of Edge. Denition 4.8 (k-Vertex Connected)A graph G is k-vertex connected if k is the small- est subset of vertices such that the deletion of same renders graph disconnected.Refer Figure

4.4 for examples.

8SV;jSj k1such that G(VnS;E)is connected:

17-5 Denition 4.9 (k-Edge Connected)LetG= (V;E)be an arbitrary graph. If subgraph G

0= (V;EnX)is connected for allXEwherejXj k1, then G is k-edge-connected.

The edge connectivity ofGis the maximum value k such that G is k-edge-connected. The smallest set X whose removal disconnects G is a minimum cut in G.Refer Figure 4.4 for examples.v 1v 3v 2v 4v 5v

6(a) 4-Edge-Connected and 2-Vertex-

Connected Graph(cut)v

6v 5v 4v 2v 3v

1(b) 2-Edge-Connected and 1-Vertex-

Connected Graph

Figure 4.4: Example of k-Edge-Connected and k-Vertex-Connected Graphv 1v 2v 3v 4v 5v 6v

7Figure 4.5: A disconnected 2-regular graph G having two components.

Solved Example 1:Find the eigenvalue and eigenvector of graph given in Figure 4.5 Solution:The adjacency matrixAof graphGgiven in Figure 4.5 is following: A=2 6

666666640 1 1 0 0 0 0

1 0 0 1 0 0 0

0 1 1 0 0 0 0

0 0 0 0 0 1 1

0 0 0 0 1 0 1

0 0 0 0 1 1 03

77777775

77
17-6 Hence, the eigenvector and the eigenvalues of adjacency matrix A can be calculated as follows: A2 6

666666641

1 1 1 1 1 13 7

77777775

71= 22

666666641

1 1 1 1 1 13 7

77777775

71and A2

666666641

1 1 1 0 0 03 7

77777775

71= 22

666666641

1 1 1 0 0 03 7

77777775

71
In general for d-Regular-GraphG(V;E),Aeigenvector=degree(V)eigenvecotor. Fact 4.10An adjacency matrix of any disconnected graph having two components resembles following matrix, whereXandYare respective adjacency matrix of disconnected compo- nents in graph.quotesdbs_dbs4.pdfusesText_8

[PDF] [PDF] Lecture 17: Introduction to Graph Theory 1 Preliminaries

Discrete Mathematics14-10-2019

Lecture 17: Introduction to Graph Theory

6Figure 1.1: Example of a Graph.

2.1 Sets and Relation

2.2 Adjacency Matrix

0otherwise(2.1)

6640 1:::0

1 0:::1

0 0:::03

2.3 Adjacency List

3 Euler's Handshaking Lemma

4 Properties of Adjacency Matrix

4.1 Square of Adjacency Matrix

2ij=j fkjAik= 1 =Akjg j(4.1)

4.2 Cube of Adjacency Matrix

3ij=j f(k;l)jAik= 1 =Akl=Aljg j(4.2)

4.3 Eigenvalue of Adjacency Matrix

3(a) 2-Regular Graph with 3 verticesv

4(b) 2-Regular Graph with 4 vertices

Figure 4.3: Example of d-Regular Graphs

4.4 for examples.

8SV;jSj k1such that G(VnS;E)is connected:

0= (V;EnX)is connected for allXEwherejXj k1, then G is k-edge-connected.

6(a) 4-Edge-Connected and 2-Vertex-

Connected Graph(cut)v

1(b) 2-Edge-Connected and 1-Vertex-

Connected Graph

7Figure 4.5: A disconnected 2-regular graph G having two components.

666666640 1 1 0 0 0 0

1 0 0 1 0 0 0

1 0 0 1 0 0 0

0 1 1 0 0 0 0

0 0 0 0 0 1 1

0 0 0 0 1 0 1

0 0 0 0 1 1 03

77777775

666666641

77777775

71= 22

666666641

77777775

71and A2

666666641

77777775

71= 22

666666641

77777775