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

Lecture Notes on Graph Theory Vadim Lozin 1 Introductory concepts A graph G = (V,E) consists of two finite sets V and E The elements of V are called the

[PDF] Graph Theory lecture notes

Graph Theory lecture notes 1 Definitions and examples 1–1 Definitions Definition 11 A graph is a set of points, called vertices, together with a collection of

[PDF] Lecture Notes Graph Theory

Dec 6, 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 - personalpsuedu - Penn State

Jul 20, 2011 · Alright, let's move on then This is a set of lecture notes for Math 485–Penn State's undergraduate Graph Theory course Since I use these notes

[PDF] Notes on graph theory

Dec 13, 2010 · A graph is a structure in which pairs of vertices are connected by edges Each edge may act like an ordered pair (in a directed graph) or an

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

Aug 2, 2016 · These are lecture notes on graph theory – the part of mathematics involved with graphs They are currently work in progress (but the parts that

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

Oct 14, 2019 · Definition 12 (Simple Graphs) A simple graph is a finite undirected graph without Graph Theory Penn State Math 485 Lecture Notes [PDF]

[PDF] Graph Theory and Applications

August 2009 Inspired from the course notes of V Blondel and L Wolsey (UCL) But now graph theory is used for finding communities in networks where we

[PDF] Lecture Notes In Graph Theory Kit - Pledge to the WFMU Marathon

Art of Counting Math 395 Category Theory Lecture Notes on Graph Theory in PDF format at lecturenotesin, Engineering Class handwritten notes, exam notes

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