Graph Theory - Revision history

Marc: /* Terminology */

2024-09-23T17:42:27Z

Terminology

← Older revision		Revision as of 10:42, 23 September 2024
Line 19:		Line 19:
	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 HEGH 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, HEGH and EHGE 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.		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 HEGH 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, HEGH and EHGE 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 and the number of edges by E. ~~Note that E can range anywhere from $V$ to $V^2$ (or $V(V-1)/2$ in an undirected graph).~~ Graphs with 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.''		We’ll denote the number of vertices in a given graph by V and the number of edges by E. Graphs with 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.''

	== Directed Graphs ==		== Directed Graphs ==

Marc: /* Other Videos */

2021-12-08T04:16:32Z

Marc: wordsmithing

2020-09-01T20:49:48Z

wordsmithing

← Older revision		Revision as of 13:49, 1 September 2020
Line 54:		Line 54:
	== Adjacency Matrices ==		== Adjacency Matrices ==

	It is frequently convenient to represent a graph by a matrix known as ~~Adjacency Matrix~~. ~~Let us understand using~~ the ~~4 node~~ directed graph ~~below~~:		It is frequently convenient to represent a graph by a matrix known as an ''adjacency matrix.'' Consider
			the following directed graph:

	[[File:DirectedGraph.png\|200px]]		[[File:DirectedGraph.png\|200px]]

	To draw adjacency matrix, we ~~put all nodes in~~ rows and ~~also arrange them in~~ columns ~~which gives a $4×4$ matrix~~ (the left ~~empty matrix~~). ~~We then put~~ 1 for ~~all~~ the ~~edges considering their direction~~ (~~see~~ the middle ~~one~~) ~~and finally put~~ 0 ~~for~~ all ~~unfilled~~ cells ~~which gives us the adjacency matrix~~ (the ~~rightmost one, highlighted~~).		To draw the adjacency matrix, we create an $N$ by $N$ grid and label the rows and columns for each vertex (diagram at the left). Then, place a 1 for each edge in the cell whose row and column correspond to the
			starting and ending vertices of the edge (diagram in the middle). Finally, place
			a 0 in all other cells (diagram at the right).

	[[File:AdjMatrix.png\|600px]]		[[File:AdjMatrix.png\|600px]]

	By construction, ~~each path of this~~ matrix is of ~~length~~ 1. ~~Now if~~ we ~~raise~~ the ~~power~~ of ~~matrix M~~ to ~~2, we get:~~		By construction, cell $(i,j)$ in the matrix with a value of 1 indicates a direct path from vertex $i$ to vertex $j$.
			If we square the
			matrix, the value in cell $(i,j)$ indicates the number of paths of length 2 from vertex $i$ to vertex $j$.

	[[File:AdjMatrix2.png\|250px]]		[[File:AdjMatrix2.png\|250px]]

	~~And this~~ says that there ~~are~~ 2 paths of length 2 from A to C~~. By examination we can see they are~~ A → B → C and A → D → C. This also says that there is exactly 1 path of length 2 from A to D ~~which is~~ A → B → D, exactly 1 path of length 2 from B to B ~~which is~~ B → C → B and so on.		For example, the $M^2$ says that there 2 paths of length 2 from A to C (A → B → C and A → D → C). This also says that there is exactly 1 path of length 2 from A to D (A → B → D), exactly 1 path of length 2 from B to B (B → C → B), and so on.

	If we raise M to the ''pth'' power, the resulting matrix indicates which paths of length ''p'' exist in the graph. The value in $M^p(i,j)$ is the number of paths from vertex ''i'' to vertex ''j''.		In general, if we raise $M$ to the ''pth'' power, the resulting matrix indicates which paths of length $p$ exist in the graph.
			The value in $M^p(i,j)$ is the number of paths from vertex $i$ to vertex $j$.

	== Sample Problems ==		== Sample Problems ==

Marc: wordsmithing

2020-09-01T20:37:29Z

wordsmithing

← Older revision		Revision as of 13:37, 1 September 2020
Line 29:		Line 29:
	This graph is defined as the set of vertices V = {A,B,C,D,E,F,G,H} and the set of edges {AB,AD,DA,DB,EG,GE,HG,HE,GF,CF,FC}. There is one directed path from G to C (namely, GFC); however, there are no directed paths from C to G. Note that a few of the edges have arrows on both ends, such as the edge between A and D. These dual arrows indicate that there is an edge in 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 directed graph with no cycles is called a ''dag'' (directed acyclic graph).		This graph is defined as the set of vertices V = {A,B,C,D,E,F,G,H} and the set of edges {AB,AD,DA,DB,EG,GE,HG,HE,GF,CF,FC}. There is one directed path from G to C (namely, GFC); however, there are no directed paths from C to G. Note that a few of the edges have arrows on both ends, such as the edge between A and D. These dual arrows indicate that there is an edge in 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 directed graph with no cycles is called a ''dag'' (directed acyclic graph).

	== Trees & ~~Forest~~ ==		== Trees & Forests ==

	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 graph with no cycles is called a ''tree''. There is only one path between any two nodes in a tree. A tree with $N$ vertices contains exactly $N-1$ edges.

	[[File:forest.png\|500px]]		[[File:forest.png\|500px]]

	The ~~graph on the left~~ shown above ~~is a tree~~ because it has no cycles and vertices are connected. It has ~~four~~ vertices and ~~three~~ edges, ~~i.e.~~, ~~for ''N'' vertices ''N-1''~~ edges ~~as mentioned in~~ the ~~definition~~.		The two graphs shown above are trees because neither has any cycles and all vertices are connected. The graph
			on the left has 4 vertices and 3 edges; the graph on the right has 8 vertices and 7 edges. Note that in both cases, because they
			are trees,
			the number of edges is one less than the number of vertices.

	A ''~~spanning tree~~'' of a graph is a subgraph that contains all the vertices and forms a tree. Minimal spanning trees can be found for weighted graphs (i.e. each edge has a cost or distance associated with it) in order to minimize the cost or distance across an entire network.		A group of disconnected trees is called a ''forest''.

	A ~~group~~ of ~~disconnected trees~~ is ~~called~~ a ''~~forest~~''.		A ''weighted graph'' is a graph that has a weight (also referred to as a cost) associated with each edge.
			For example, in a graph
			used by airlines where cities are vertices and edges are cities with direct flights connecting them,
			the weight for each edge might be the distance between the cities.

			A ''spanning tree'' of a graph is a subgraph that contains all the vertices and forms a tree.
			A ''minimal spanning tree''
			can be found for weighted graphs
			in order to minimize the cost across an entire network.

	== Adjacency Matrices ==		== Adjacency Matrices ==

Marc: wordsmith 1st paragraph; used mathtype in last paragraph

2020-09-01T18:48:23Z

wordsmith 1st paragraph; used mathtype in last paragraph

← Older revision		Revision as of 11:48, 1 September 2020
Line 11:		Line 11:
	== Terminology ==		== Terminology ==

	The edges of the above graph ~~has~~ no directions meaning the edge from one vertex A to another vertex B is the same as from vertex B to vertex A. ~~So the~~ graph ~~above~~ is an ''undirected graph''. Similarly ~~graphs~~ having a direction associated with each edge is known as ''directed graph'' ~~(see section below)~~.		The edges of the above graph have no directions meaning that the edge from one vertex A to another vertex B is the same as from vertex B to vertex A. Such a graph is called an ''undirected graph''. Similarly, a graph having a direction associated with each edge is known as a ''directed graph''.

	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, FGHE is path from F to E in the graph above. A ''simple path'' is a path with no vertex repeated. For example, FGHEG is not a simple path.		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, FGHE is path from F to E in the graph above. A ''simple path'' is a path with no vertex repeated. For example, FGHEG is not a simple path.
Line 19:		Line 19:
	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 HEGH 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, HEGH and EHGE 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.		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 HEGH 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, HEGH and EHGE 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 and the number of edges by E. Note that E can range anywhere from V to V~~<sup>~~2~~</sup>~~ (or V(V-1)/2 in an undirected graph). Graphs with 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.''		We’ll denote the number of vertices in a given graph by V and the number of edges by E. Note that E can range anywhere from $V$ to $V^2$ (or $V(V-1)/2$ in an undirected graph). Graphs with 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.''

	== Directed Graphs ==		== Directed Graphs ==

Partha: /* Problem 2 */

2020-09-01T01:02:44Z

Problem 2

← Older revision		Revision as of 18:02, 31 August 2020
Line 103:		Line 103:
	[[File:matrix_s3.png]]		[[File:matrix_s3.png]]

	There is 1 path of length 2 from A to C (cell [1,3] in $M^2$). By inspection, the only path of length 2 is A->A->C.		There is 1 path of length 2 from A to C (cell [1,3] in $M^2$). By inspection, the only path of length 2 is A → A → C.

	There are 3 paths of length 4 (cell [1,3] in $M^4$) and they are A->A->A->A->C, A->A->C->A->C, A->C->A->A->C.		There are 3 paths of length 4 (cell [1,3] in $M^4$) and they are A → A → A → A → C, A → A → C → A → C, A → C → A → A → C.

	=== Problem 3 ===		=== Problem 3 ===

Partha: /* Adjacency Matrices */

2020-09-01T01:01:09Z

Adjacency Matrices

← Older revision		Revision as of 18:01, 31 August 2020
Line 47:		Line 47:
	[[File:DirectedGraph.png\|200px]]		[[File:DirectedGraph.png\|200px]]

	To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a ~~4x4~~ matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).		To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a $4×4$ matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).

	[[File:AdjMatrix.png\|600px]]		[[File:AdjMatrix.png\|600px]]

	Bu construction, each path of this matrix is of length 1. Now if we raise the power of matrix M to 2, we get:		By construction, each path of this matrix is of length 1. Now if we raise the power of matrix M to 2, we get:

	[[File:AdjMatrix2.png\|250px]]		[[File:AdjMatrix2.png\|250px]]

	And this says that there are 2 paths of length 2 from A to C. By examination we can see they are A->B->C and A->D->C. This also says that there is exactly 1 path of length 2 from A to D which is A->B->D, exactly 1 path of length 2 from B to B which is B~~->c->~~B and so on.		And this says that there are 2 paths of length 2 from A to C. By examination we can see they are A → B → C and A → D → C. This also says that there is exactly 1 path of length 2 from A to D which is A → B → D, exactly 1 path of length 2 from B to B which is B → C → B and so on.

	If we raise M to the ''pth'' power, the resulting matrix indicates which paths of length ''p'' exist in the graph. The value in $M^p(i,j)$ is the number of paths from vertex ''i'' to vertex ''j''.		If we raise M to the ''pth'' power, the resulting matrix indicates which paths of length ''p'' exist in the graph. The value in $M^p(i,j)$ is the number of paths from vertex ''i'' to vertex ''j''.

Partha: /* Adjacency Matrices */

2020-09-01T00:22:10Z

Adjacency Matrices

← Older revision		Revision as of 17:22, 31 August 2020
Line 45:		Line 45:
	It is frequently convenient to represent a graph by a matrix known as Adjacency Matrix. Let us understand using the 4 node directed graph below:		It is frequently convenient to represent a graph by a matrix known as Adjacency Matrix. Let us understand using the 4 node directed graph below:

	[[File:DirectedGraph.png\|~~300px~~]]		[[File:DirectedGraph.png\|200px]]

	To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a 4x4 matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).		To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a 4x4 matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).

Partha: /* Adjacency Matrices */

2020-08-31T23:48:44Z

Adjacency Matrices

← Older revision		Revision as of 16:48, 31 August 2020
Line 43:		Line 43:
	== Adjacency Matrices ==		== 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 an edge from vertex ''i'' to ''j''., whereas a "zero" indicates there is not an edge. If we raise M to the ''pth'' power, the resulting matrix indicates which paths of length ''p'' exist in the graph~~. The value in $M^p(i,j)$ is the number of paths from vertex ''i'' to vertex ''j''.~~		It is frequently convenient to represent a graph by a matrix known as Adjacency Matrix. Let us understand using the 4 node directed graph below:

			[[File:DirectedGraph.png\|300px]]

	~~It is frequently convenient to represent a graph by~~ a matrix ~~known as Adjacency Matrix~~. ~~Let~~ us ~~understand using~~ the ~~4 node directed graph below:~~		To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a 4x4 matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).

	[[File:~~DirectedGraph~~.png\|~~250px~~]]		[[File:AdjMatrix.png\|600px]]

	~~To draw adjacency matrix~~, ~~we put all nodes in rows and also arrange them in columns which gives a 4x4~~ matrix ~~(the left empty matrix)~~. ~~We then put 1 for all~~ the ~~edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency~~ matrix ~~(the rightmost one~~, ~~highlighted).~~		Bu construction, each path of this matrix is of length 1. Now if we raise the power of matrix M to 2, we get:

	~~[[File~~:~~AdjMatrix.png\|600px]]~~

	~~Bu construction, each path of this matrix is of length 1~~. ~~Now if we raise the power of matrix M to 2, we get:~~		[[File:AdjMatrix2.png\|250px]]

	~~[[File:AdjMatrix2~~.~~png\|300px]]~~		And this says that there are 2 paths of length 2 from A to C. By examination we can see they are A->B->C and A->D->C. This also says that there is exactly 1 path of length 2 from A to D which is A->B->D, exactly 1 path of length 2 from B to B which is B->c->B and so on.

	~~And this says that there are 2~~ paths of length ~~2 from A to C~~. ~~By examination we can see they are A->B->C and A->D->C. This also says that there~~ is ~~exactly 1 path~~ of ~~length 2 from A to D which is A->B->D, exactly 1 path of length 2~~ from B to ~~B which is B->c->B and so on~~.		If we raise M to the ''pth'' power, the resulting matrix indicates which paths of length ''p'' exist in the graph. The value in $M^p(i,j)$ is the number of paths from vertex ''i'' to vertex ''j''.

	== Sample Problems ==		== Sample Problems ==

Partha: /* Adjacency Matrices */

2020-08-31T23:46:37Z

Adjacency Matrices

← Older revision		Revision as of 16:46, 31 August 2020
Line 52:		Line 52:
	To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a 4x4 matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).		To draw adjacency matrix, we put all nodes in rows and also arrange them in columns which gives a 4x4 matrix (the left empty matrix). We then put 1 for all the edges considering their direction (see the middle one) and finally put 0 for all unfilled cells which gives us the adjacency matrix (the rightmost one, highlighted).

	[[File:AdjMatrix.png\|~~200px~~]]		[[File:AdjMatrix.png\|600px]]

	Bu construction, each path of this matrix is of length 1. Now if we raise the power of matrix M to 2, we get:		Bu construction, each path of this matrix is of length 1. Now if we raise the power of matrix M to 2, we get:

← Older revision		Revision as of 21:16, 7 December 2021
Line 179:		Line 179:

	{\|		{\|
	\|-
	~~\| <youtube width="300" height="180">https://youtu.be/44sQJK4BycY</youtube>~~
	~~\| [https://youtu.be/44sQJK4BycY ''CS 106B Lecture: Graphs: basic concepts'']~~

	This lecture from Stanford University is s wonderful introduction to graph theory. The lecture starts out with many examples of real world problems that are modeled by graphs, and then moves on to review basic terminology relating to graph theory.
	\|-		\|-
	\| <youtube width="300" height="180"> https://youtu.be/gXgEDyodOJU</youtube>		\| <youtube width="300" height="180"> https://youtu.be/gXgEDyodOJU</youtube>