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

Свойства

Читайте также:
  1. III. Коллигативные свойства растворов
  2. Аминокислотный состав белков. Строение, стереохимия, физико-химические свойства и классификация протеиногенных аминокислот.
  3. Важнейшие свойства систем
  4. Влияние углерода и постоянных примесей на свойства сталей
  5. Глава 5. Классификация и свойства эмоций
  6. Глава 5. Классификация и свойства эмоций
  7. Глава S. Эмоциональные свойства человека

· Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины. Поэтому двудольный граф не может содержать клику размером более 2.

· Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум)

· Граф разбивается на пары разноцветных вершин тогда и только тогда, когда любые элементов одной из долей связаны по крайней мере с элементами другой (Теорема Холла).

· Полный двудольный граф, у которого в каждой части больше 2 вершин, является непланарным.

· Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

8) Теорема Кенинга о двудольности:

 

1) В любом двудольном графе число рёбер в максимальном паросочетании равно числу вершин в минимальном вершинном покрытии.

2) Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины

Если прямоугольная матрица составлена из нулей и единиц, то минимальное число линий, содержащих все единицы, равно максимальному числу единиц, которые могут быть выбраны так, чтобы никакие две из них не лежали на одной и той же линии (термин "линия" обозначает либо строку, либо столбец в матрице). [4]

Данная формулировка легко переводится на язык двудольных графов:

Строки таблицы – это вершины одной части двудольного графа, столбцы – другой части.

Линии – это вершинное покрытие.

Единицы матрицы – рёбра. Требование, чтобы никакие две единицы не лежали на одной линии соответствует паросочетанию.


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


<== предыдущая страница | следующая страница ==>
ДИФРАКЦИЯ ФРАУНГОФЕРА НА ОДНОЙ ЩЕЛИ| Экономическая сущность транспортного налога. Налогоплательщики и объект транспортного налога.

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