Basic graph definitions - Revision history

Weihe at 14:47, 16 May 2015

2015-05-16T14:47:02Z

← Older revision		Revision as of 14:47, 16 May 2015
Line 5:		Line 5:
	== Directed and undirected graphs ==		== Directed and undirected graphs ==

	# A '''directed graph''' <math>G=(V,A)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets\|multiset]] <math>A</math> of [[Sets and sequences#Singleton, pair, triple\|ordered pairs]] of nodes. The elements of <math>A</math> are the '''arcs''' of <math>G</math>.		# A '''directed graph''' <math>G=(V,A)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets\|multiset]] <math>A</math> of [[Sets and sequences#Singleton, pair, triple, quadruple\|ordered pairs]] of nodes. The elements of <math>A</math> are the '''arcs''' of <math>G</math>.
	# An undirected graph <math>G=(V,E)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets\|multiset]] <math>E</math> of [[Sets and sequences#Singleton, pair, triple\|''un''ordered pairs]] of nodes, the '''edges''' of <math>G</math>.		# An undirected graph <math>G=(V,E)</math> consists of a finite set <math>V</math> of '''nodes''' (a.k.a. '''vertices''') and a [[Sets and sequences#Sets and multisets\|multiset]] <math>E</math> of [[Sets and sequences#Singleton, pair, triple, quadruple\|''un''ordered pairs]] of nodes, the '''edges''' of <math>G</math>.
	# A directed or undirected graph is '''simple''', if:		# A directed or undirected graph is '''simple''', if:
	## No node is paired with itself in <math>A</math> or <math>E</math>, respectively.		## No node is paired with itself in <math>A</math> or <math>E</math>, respectively.

Weihe: /* Adjacency, incidence, and degree */

2014-12-06T14:04:59Z

Adjacency, incidence, and degree

← Older revision		Revision as of 14:04, 6 December 2014
Line 30:		Line 30:

	'''Remark:'''		'''Remark:'''
	In many algorithmic problems on graphs, isolated nodes may be removed before the algorithm ~~proper~~ commences.		In many algorithmic problems on graphs, isolated nodes may be removed before the algorithm commences.

	== Representations of graphs ==		== Representations of graphs ==

Weihe: /* Adjacency, incidence, and degree */

2014-12-06T14:04:03Z

Adjacency, incidence, and degree

← Older revision		Revision as of 14:04, 6 December 2014
Line 22:		Line 22:
	## An arc <math>(v,w)\in A</math> is an '''outgoing arc''' of <math>v</math>, and an '''incoming arc''' of <math>w</math>.		## An arc <math>(v,w)\in A</math> is an '''outgoing arc''' of <math>v</math>, and an '''incoming arc''' of <math>w</math>.
	## The '''outdegree''' of a node <math>v\in V</math> is the number of its outgoing arcs, the '''indegree''' of <math>v</matH> is the number of its incoming arcs.		## The '''outdegree''' of a node <math>v\in V</math> is the number of its outgoing arcs, the '''indegree''' of <math>v</matH> is the number of its incoming arcs.

			'''Statement:'''
			If there are no [[#Adjacency, incidence, and degree\|isolated nodes]], the number of edges/arcs dominates the number of nodes asymptotically.

			'''Proof:'''
			In this case, the number of edges/arcs is at least half the number of nodes.

			'''Remark:'''
			In many algorithmic problems on graphs, isolated nodes may be removed before the algorithm proper commences.

	== Representations of graphs ==		== Representations of graphs ==

Weihe: /* Connectedness */

2014-12-06T14:02:51Z

Connectedness

← Older revision		Revision as of 14:02, 6 December 2014
Line 96:		Line 96:
	'''Remark:'''		'''Remark:'''
	Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.		Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.

	~~'''Statement:'''~~
	~~If there are no [[#Adjacency, incidence, and degree\|isolated nodes]], the number of edges/arcs dominates the number of nodes asymptotically.~~

	~~'''Proof:'''~~
	~~In this case, the number of edges/arcs is at least half the number of nodes.~~

	== Bipartite and k-partite graphs ==		== Bipartite and k-partite graphs ==

Weihe at 14:01, 6 December 2014

2014-12-06T14:01:55Z

← Older revision		Revision as of 14:01, 6 December 2014
Line 67:		Line 67:
	# An undirected or directed graph is '''acyclic''' (a.k.a. '''cycle-free''') if it contains no ordinary cycle. In the directed case, an acyclic graph is usually called a '''DAG''' (short for directed acyclic graph).		# An undirected or directed graph is '''acyclic''' (a.k.a. '''cycle-free''') if it contains no ordinary cycle. In the directed case, an acyclic graph is usually called a '''DAG''' (short for directed acyclic graph).
	# For <math>s,t\in V</math>, an '''<math>(s,t)</math>-graph''' <math>G=(V,A)</math> is a DAG such that <math>s</math> is the only node with indegree zero, and <math>t</math> is the only node with outdegree zero. It is easy to see that a DAG is an <math>(s,t)</math>-graph if, and only if, <math>G</math> is the union of (not necessarily internally node-disjoint or arc-disjoint) <math>(s,t)</math>-paths.		# For <math>s,t\in V</math>, an '''<math>(s,t)</math>-graph''' <math>G=(V,A)</math> is a DAG such that <math>s</math> is the only node with indegree zero, and <math>t</math> is the only node with outdegree zero. It is easy to see that a DAG is an <math>(s,t)</math>-graph if, and only if, <math>G</math> is the union of (not necessarily internally node-disjoint or arc-disjoint) <math>(s,t)</math>-paths.

			== Forests, trees, branchings, arborescences ==

			# A '''forest''' is a [[#Cycles\|cycle-free]] undirected graph. A '''tree''' is a connected forest.
			# A '''branching''' is a [[#Cycles\|cycle-free]] directed graph such that the indegree of each node is zero or one. An '''arborescence''' is a branching such that exactly one node has indegree zero (note that, for branchings, this condition is equivalent to weak connectedness). Arborescences are also known as '''rooted trees''', and the unique node with indegree zero is the '''root'''.
			# A forest/tree/branching/arborescence '''in a graph''' <math>G</math> is a subgraph of <math>G</math> that is a forest/tree/branching/arborescence. A forest/tree/branching/arborescence is '''spanning''' if it contains all nodes of <math>G</math> (cf. [[#Subgraphs\|here]]).

			'''Statement:'''
			For a forest, let <math>n</math> denote the number of nodes, <math>m</math> the number of edges, and <math>k</math> the number of trees in this forest. Then it is <math>m=n-k</math>. In particular, for a tree, it is <math>m=n-1</math>.

			'''Proof:'''
			Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.

	== Connectedness ==		== Connectedness ==
Line 84:		Line 96:
	'''Remark:'''		'''Remark:'''
	Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.		Inclusion-maximality of the connected components implies that, in each case, the connected components form a partition of the node set.

	~~== Forests, trees, branchings, arborescences ==~~

	~~# A '''forest''' is a [[#Cycles\|cycle-free]] undirected graph. A '''tree''' is a connected forest.~~
	# A '''branching''' is a [[#Cycles\|cycle-free]] directed graph such that the indegree of each node is zero or one. An '''arborescence''' is a branching such that exactly one node has indegree zero (note that, for branchings, this condition is equivalent to weak connectedness). Arborescences are also known as '''rooted trees''', and the unique node with indegree zero is the '''root'''.
	# A forest/tree/branching/arborescence '''in a graph''' <math>G</math> is a subgraph of <math>G</math> that is a forest/tree/branching/arborescence. A forest/tree/branching/arborescence is '''spanning''' if it contains all nodes of <math>G</math> (cf. [[#Subgraphs\|here]]).

	'''Statement:'''		'''Statement:'''
	~~For a forest~~, ~~let <math>n</math> denote the number of~~ nodes, ~~<math>m</math>~~ the number of edges~~, and <math>k<~~/~~math>~~ the number of ~~trees in this forest. Then it is <math>m=n-k</math>. In particular, for a tree, it is <math>m=n-1</math>~~.		If there are no [[#Adjacency, incidence, and degree\|isolated nodes]], the number of edges/arcs dominates the number of nodes asymptotically.

	'''Proof:'''		'''Proof:'''
	~~Obviously~~, ~~it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on~~ the number ~~<math>n\geq 1</math>~~ of ~~nodes. For <math>n=1</math>, it is <math>m=0<~~/~~math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there~~ is ~~a longest path <math>p</math> in terms of~~ the number of ~~edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. Removing one of these~~ nodes ~~along with its unique incident edge and applying the induction hypothesis yields the claim~~.		In this case, the number of edges/arcs is at least half the number of nodes.

	== Bipartite and k-partite graphs ==		== Bipartite and k-partite graphs ==

Weihe: /* Forests, trees, branchings, arborescences */

2014-12-06T13:54:51Z

Forests, trees, branchings, arborescences

← Older revision		Revision as of 13:54, 6 December 2014
Line 92:		Line 92:

	'''Statement:'''		'''Statement:'''
	For a forest, let <math>n</math> denote the number of nodes, <math>m</math> the number of edges, and <math>k</math> the number of ~~[[#Connectedness\|connected components]]~~. Then it is <math>m=n-k</math>. In particular, for a tree, it is <math>m=n-1</math>.		For a forest, let <math>n</math> denote the number of nodes, <math>m</math> the number of edges, and <math>k</math> the number of trees in this forest. Then it is <math>m=n-k</math>. In particular, for a tree, it is <math>m=n-1</math>.

	'''Proof:'''		'''Proof:'''

Weihe: /* Adjacency, incidence, and degree */

2014-12-06T11:32:21Z

Adjacency, incidence, and degree

← Older revision		Revision as of 11:32, 6 December 2014
Line 17:		Line 17:
	# A node and an arc/edge are called '''incident''' if the node belongs to the arc/edge.		# A node and an arc/edge are called '''incident''' if the node belongs to the arc/edge.
	# Two arcs/edges are called '''incident''' if they share at least one node.		# Two arcs/edges are called '''incident''' if they share at least one node.
	# For a node, the number of incident arcs/edges is the '''degree''' of this node.		# For a node, the number of incident arcs/edges is the '''degree''' of this node. A node with degree zero is '''isolated'''.
	# Consider a directed graph <math>G=(V,A)</math>:		# Consider a directed graph <math>G=(V,A)</math>:
	## For an arc <math>a=(v,w)\in A</math>, <math>v</math> is the '''tail''' of <math>a</math>, and <math>w</math> is the '''head''' of <math>a</math>.		## For an arc <math>a=(v,w)\in A</math>, <math>v</math> is the '''tail''' of <math>a</math>, and <math>w</math> is the '''head''' of <math>a</math>.

Weihe: /* Forests, trees, branchings, arborescences */

2014-12-06T11:30:02Z

Forests, trees, branchings, arborescences

← Older revision		Revision as of 11:30, 6 December 2014
Line 95:		Line 95:

	'''Proof:'''		'''Proof:'''
	Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have ~~degree one. In particular, ''there are'' nodes with~~ degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.		Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.

	== Bipartite and k-partite graphs ==		== Bipartite and k-partite graphs ==

Weihe: /* Forests, trees, branchings, arborescences */

2014-12-06T11:29:47Z

Forests, trees, branchings, arborescences

← Older revision		Revision as of 11:29, 6 December 2014
Line 95:		Line 95:

	'''Proof:'''		'''Proof:'''
	Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. In particular, there are nodes with degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.		Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. In particular, ''there are'' nodes with degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.

	== Bipartite and k-partite graphs ==		== Bipartite and k-partite graphs ==

Weihe: /* Forests, trees, branchings, arborescences */

2014-12-06T11:29:27Z

Forests, trees, branchings, arborescences

← Older revision		Revision as of 11:29, 6 December 2014
Line 95:		Line 95:

	'''Proof:'''		'''Proof:'''
	Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. ~~Since~~ <math>p</math> is ~~nozt extendible~~, its two end nodes have degree one. In particular, there are nodes with degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.		Obviously, it suffices to prove <math>m=n-1</math> for trees. This is proved by an induction on the number <math>n\geq 1</math> of nodes. For <math>n=1</math>, it is <math>m=0</math>, so consider the case <math>n>1</math>. Since there are no cycles, the set of all possible paths in a tree is finite. Therefore, there is a longest path <math>p</math> in terms of the number of edges. Then <math>p</math> is not extensible, so its two end nodes have degree one. In particular, there are nodes with degree one. Removing one of these nodes along with its unique incident edge and applying the induction hypothesis yields the claim.

	== Bipartite and k-partite graphs ==		== Bipartite and k-partite graphs ==