Аноним

Competition graph (of a tournament): различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''Competition graph (of a tournament)''' --- граф конкуренции. Let <math>O(x)</math> be the set of vertices that <math>x</math> beats. Given a tour…»)
 
Нет описания правки
 
Строка 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.