Графоид

Графоид (Graphoid) — комбинаторный объект, состоящий из непустого множества [math]\displaystyle{ M }[/math] и двух семейств [math]\displaystyle{ \mathcal{C} }[/math] и [math]\displaystyle{ \mathcal {D} }[/math] непустых подмножеств множества [math]\displaystyle{ M }[/math], называемых соответственно циклами и коциклами, которые удовлетворяют следующим аксиомам:

1) [math]\displaystyle{ |C \cap D| \neq 1 }[/math] для любых [math]\displaystyle{ C \in \mathcal{C} }[/math] и [math]\displaystyle{ D \in \mathcal {D} }[/math];

2) ни один из циклов не является собственной частью другого цикла и ни один коцикл не является собственной частью другого коцикла;

3) если раскрасить элементы множества [math]\displaystyle{ M }[/math] так, что точно один элемент будет зеленого цвета, а остальные красного или синего, то найдется либо цикл [math]\displaystyle{ C }[/math], содержащий зеленый элемент и не содержащий ни одного красного, либо коцикл [math]\displaystyle{ D }[/math], содержащий зеленый элемент и не содержащий ни одного синего.

Литература

• Харари Ф. Теория графов. — М.: Мир, 1973.