Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Тема 13.3. Отношения порядка и эквивалентности на графе

Тема 10.1. Задача получения продукции | Тема 10.2. Решение задачи о продукции | Раздел 11. Теория релейно-контактных схем | Тема 11.4. Двоичный сумматор | Тема 11.5. Методы упрощения логических выражений. Методы решения логических задач | Тема 12.1. Определение предиката | Тема 12.2. Логические операции над предикатами | Тема 12.3. Кванторы | Тема 12.4. Истинные формулы и эквивалентные соотношения | Тема 12.5. Доказательства в логике предикатов |


Читайте также:
  1. C. Л. Франк Понятие философии. Взаимоотношения философии и науки
  2. II. Сфера действия Порядка
  3. III. Потенциально опасные взаимоотношения.
  4. А ведь именно в отношениях человек и раскрывается как личность, в отношениях с себе подобными он более всего проявляет свою божественность.
  5. А отношения с мачехой?
  6. Административно-правовые отношения
  7. Актуальные отношения и контрперенос

Граф даёт удобное геометрическое представление отношений на множестве. Будем считать, что на графе введено отношение порядка, если для любых двух вершин и , удовлетворяющих условию , существует путь из в . В этом случае говорят, что вершина предшествует вершине , или что следует за вершиной . Покажем, что данное определение отражает на графе все свойства отношения порядка.

Рефлексивность: Условие – истинно. Это означает эквивалентность вершины самой себе. Однако, при желании, это условие можно рассматривать как наличие петли в вершине .

Транзитивность: Условие «если и , то » означает, что вершины последовательно встречаются на одном и том же пути.

Антисимметричность: «если и , то ». Левая часть этого выражения говорит о том, что существует путь из в и путь из в . Т.о. в графе существует контур, на котором лежат вершины и . Из правой части свойства вытекает, что вершины лежащие на одном контуре – эквивалентны. Будем рассматривать этот вывод, как определение отношения эквивалентности на графе и покажем, что такое определение удовлетворяет всем условиям отношения эквивалентности.

Рефлексивность: Условие – вытекает из определения отношения эквивалентности. Всегда можно считать, что существует путь из в длины 0.

Транзитивность: Условие «если и , то » так же очевидно, так как если в графе есть контур, содержащий вершины и , и есть контур, содержащий и , то существует контур, содержащий вершины и .

Симметричность: Условие «если , то Þ » так же очевидно и вытекает из определения отношения эквивалентности и понятия контура графа.

Таким образом, отношения порядка и эквивалентности определяют некоторый связный граф.

На графе может быть также введено отношение строгого порядка. В этом случае для любых двух вершин и , удовлетворяющих условию , существует путь, идущий из в . В этом случае условие антирефлексивности означает отсутствие петель, а условие несимметричности говорит об отсутствии контуров. Т.о. отношение строгого порядка определяет граф без петель и контуров.


Дата добавления: 2015-10-28; просмотров: 75 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Тема 13.1. Основные определения теории графов| Тема 14.1. Граф достижимости

mybiblioteka.su - 2015-2024 год. (0.009 сек.)