Competition graph (of a tournament): различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Competition graph (of a tournament)''' --- граф конкуренции. Let <math>O(x)</math> be the set of vertices that <math>x</math> beats. Given a tour…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Competition graph (of a tournament)''' | '''Competition graph (of a tournament)''' — ''[[граф конкуренции]].'' | ||
Let <math>O(x)</math> be the set of vertices that <math>x</math> beats. | Let <math>\,O(x)</math> be the set of [[vertex|vertices]] that <math>\,x</math> beats. Given a [[tournament]] <math>\,T</math> with a vertex set <math>\,V(T)</math>, the '''competition graph''' of <math>\,T</math>, denoted <math>\,C(T)</math>, is the [[graph, undirected graph, nonoriented graph|graph]] on <math>\,V(T)</math> with an [[edge]] between vertices <math>\,x</math> and <math>\,y</math> if and only if <math>\,O(x) \cap O(y) \neq \emptyset</math>. It is known that the ''[[complement of a graph, complementary graph|complement]]'' of the '''competition graph''' is the ''[[domination graph]]''. | ||
Given a tournament <math>T</math> with a vertex set <math>V(T)</math>, the '''competition graph''' of <math>T</math>, | |||
denoted <math>C(T)</math>, is the graph on <math>V(T)</math> with an edge between vertices | |||
<math>x</math> and <math>y</math> if and only if <math>O(x) \cap O(y) \neq \emptyset</math>. It is known that the ''complement'' of the '''competition graph''' is the ''domination graph''. | |||
For an arbitrary acyclic digraph <math>D</math>, the '''competition graph''' of <math>D</math> has the same set of vertices as <math>D</math> and an edge between vertices <math>u</math> and <math>v</math> if and only if there is a vertex <math>x</math> in <math>D</math> such that <math>(u,x)</math> and <math>(v,x)</math> are arcs of <math>D</math>. The '''competition number''' of a graph <math>G</math>, denoted by <math>k(G)</math>, is the smallest number <math>k</math> such that <math>G</math> with <math>k</math> isolated vertices is a competition graph of an acyclic digraph. | For an arbitrary [[acyclic graph|acyclic]] [[digraph]] <math>\,D</math>, the '''competition graph''' of <math>\,D</math> has the same set of vertices as <math>\,D</math> and an edge between vertices <math>\,u</math> and <math>\,v</math> if and only if there is a vertex <math>\,x</math> in <math>\,D</math> such that <math>\,(u,x)</math> and <math>\,(v,x)</math> are [[arc|arcs]] of <math>\,D</math>. The '''[[competition number]]''' of a graph <math>\,G</math>, denoted by <math>\,k(G)</math>, is the smallest number <math>\,k</math> such that <math>\,G</math> with <math>\,k</math> [[isolated vertex|isolated vertices]] is a competition graph of an acyclic digraph. | ||
The '''competition-common enemy graph''' of <math>D</math> has the same set of | The '''[[competition-common enemy graph]]''' of <math>\,D</math> has the same set of vertices as <math>\,D</math> and an edge between vertices <math>\,u</math> and <math>\,v</math> if and only if there are vertices <math>\,w</math> and <math>\,x</math> in <math>\,D</math> such that <math>\,(w,u)</math>, <math>\,(w,v)</math>, <math>\,(u,x)</math> and <math>\,(v,x)</math> are arcs in <math>\,D</math>. The '''[[double competition number]]''' of a graph <math>\,G</math>, denoted by | ||
vertices as <math>D</math> and an edge between vertices <math>u</math> and <math>v</math> if and only if there are vertices <math>w</math> and <math>x</math> in <math>D</math> such that <math>(w,u)</math>, <math>(w,v)</math>, <math>(u,x)</math> and <math>(v,x)</math> are arcs in <math>D</math>. The '''double competition number''' of a graph <math>G</math>, denoted by | <math>\,dk(G)</math>, is the smallest number <math>\,k</math> such that <math>\,G</math> with <math>\,k</math> isolated vertices is a competition-common enemy graph of an acyclic digraph. It is known that <math>\,dk(G) \leq k(G) + 1</math> for any graph <math>\,G</math>. | ||
<math>dk(G)</math>, is the smallest number <math>k</math> such that <math>G</math> with <math>k</math> isolated vertices is a competition-common enemy graph of an acyclic digraph. It is known | |||
that <math>dk(G) \leq k(G) + 1</math> for any graph <math>G</math>. | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:58, 5 ноября 2014
Competition graph (of a tournament) — граф конкуренции.
Let [math]\displaystyle{ \,O(x) }[/math] be the set of vertices that [math]\displaystyle{ \,x }[/math] beats. Given a tournament [math]\displaystyle{ \,T }[/math] with a vertex set [math]\displaystyle{ \,V(T) }[/math], the competition graph of [math]\displaystyle{ \,T }[/math], denoted [math]\displaystyle{ \,C(T) }[/math], is the graph on [math]\displaystyle{ \,V(T) }[/math] with an edge between vertices [math]\displaystyle{ \,x }[/math] and [math]\displaystyle{ \,y }[/math] if and only if [math]\displaystyle{ \,O(x) \cap O(y) \neq \emptyset }[/math]. It is known that the complement of the competition graph is the domination graph.
For an arbitrary acyclic digraph [math]\displaystyle{ \,D }[/math], the competition graph of [math]\displaystyle{ \,D }[/math] has the same set of vertices as [math]\displaystyle{ \,D }[/math] and an edge between vertices [math]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math] if and only if there is a vertex [math]\displaystyle{ \,x }[/math] in [math]\displaystyle{ \,D }[/math] such that [math]\displaystyle{ \,(u,x) }[/math] and [math]\displaystyle{ \,(v,x) }[/math] are arcs of [math]\displaystyle{ \,D }[/math]. The competition number of a graph [math]\displaystyle{ \,G }[/math], denoted by [math]\displaystyle{ \,k(G) }[/math], is the smallest number [math]\displaystyle{ \,k }[/math] such that [math]\displaystyle{ \,G }[/math] with [math]\displaystyle{ \,k }[/math] isolated vertices is a competition graph of an acyclic digraph.
The competition-common enemy graph of [math]\displaystyle{ \,D }[/math] has the same set of vertices as [math]\displaystyle{ \,D }[/math] and an edge between vertices [math]\displaystyle{ \,u }[/math] and [math]\displaystyle{ \,v }[/math] if and only if there are vertices [math]\displaystyle{ \,w }[/math] and [math]\displaystyle{ \,x }[/math] in [math]\displaystyle{ \,D }[/math] such that [math]\displaystyle{ \,(w,u) }[/math], [math]\displaystyle{ \,(w,v) }[/math], [math]\displaystyle{ \,(u,x) }[/math] and [math]\displaystyle{ \,(v,x) }[/math] are arcs in [math]\displaystyle{ \,D }[/math]. The double competition number of a graph [math]\displaystyle{ \,G }[/math], denoted by [math]\displaystyle{ \,dk(G) }[/math], is the smallest number [math]\displaystyle{ \,k }[/math] such that [math]\displaystyle{ \,G }[/math] with [math]\displaystyle{ \,k }[/math] isolated vertices is a competition-common enemy graph of an acyclic digraph. It is known that [math]\displaystyle{ \,dk(G) \leq k(G) + 1 }[/math] for any graph [math]\displaystyle{ \,G }[/math].
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.