Графоид: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Графоид''' (''Graphoid'') - комбинаторный объект, состоящий из непустого множест...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Графоид''' (''Graphoid'') | '''Графоид''' (''[[Graphoid]]'') — комбинаторный объект, состоящий из непустого множества <math>M</math> и двух семейств <math>\mathcal{C}</math> и <math>\mathcal {D}</math> непустых подмножеств множества <math>M</math>, называемых соответственно [[цикл|циклами]] и [[коцикл|коциклами]], которые | ||
комбинаторный объект, состоящий из непустого множества <math>M</math> и двух | |||
семейств <math>{ | |||
<math>M</math>, называемых соответственно циклами и коциклами, которые | |||
удовлетворяют следующим аксиомам: | удовлетворяют следующим аксиомам: | ||
1) <math>|C \cap D| \neq 1</math> для любых <math>C \in { | 1) <math>|C \cap D| \neq 1</math> для любых <math>C \in \mathcal{C}</math> и <math>D \in \mathcal {D}</math>; | ||
2) ни один из циклов не является собственной частью другого цикла | 2) ни один из циклов не является собственной частью другого цикла и ни один коцикл не является собственной частью другого коцикла; | ||
и ни один коцикл не является собственной частью другого коцикла; | |||
3) если раскрасить элементы множества <math>M</math> так, что точно один | 3) если раскрасить элементы множества <math>M</math> так, что точно один элемент будет зеленого цвета, а остальные красного или синего, то найдется либо цикл <math>C</math>, содержащий зеленый элемент и не содержащий ни одного красного, либо коцикл <math>D</math>, содержащий зеленый элемент и не содержащий ни одного синего. | ||
элемент будет зеленого цвета, а остальные красного или синего, то | |||
найдется либо цикл <math>C</math>, содержащий зеленый элемент и не содержащий | |||
ни одного красного, либо коцикл <math>D</math>, содержащий зеленый элемент и | |||
не содержащий ни одного синего. | |||
==Литература== | ==Литература== | ||
* Харари Ф. Теория графов. — М.: Мир, 1973. | |||
Текущая версия от 14:14, 2 февраля 2011
Графоид (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.