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

Теорема. Пусть G — граф, а AG — его матрица инциденций

Читайте также:
  1. II закон термодинамики. Теорема Карно-Клаузиуса
  2. Доказательство. Теорема.
  3. Интегральная теорема Лапласа
  4. Котельников теоремасы бойынша санақ шығарудың жиілігін таңдау
  5. ЛЕКЦИЯ 12. ТЕОРЕМА О ПЛОТНОСТИ СУММЫ ДВУХ СЛУЧАЙНЫХ ВЕЛИЧИН
  6. ЛЕКЦИЯ 18. ЦЕНТРАЛЬНАЯ ПРЕДЕЛЬНАЯ ТЕОРЕМА
  7. ЛЕКЦИЯ 6. ИНТЕГРАЛЬНАЯ ТЕОРЕМА МУАВРА–ЛАПЛАСА, ТЕОРЕМА БЕРНУЛЛИ

Пусть G — граф, а AG — его матрица инциденций. Если рассматривать AG как матрицу над полем {0, 1}, где все операции выполняются по модулю 2, то тогда векторный матроид, построенный на AG, в качестве независимых множеств будет содержать множества ребер, не содержащих в себе циклов, и M(G) = M[AG].

Доказательство. Необходимо доказать, что XAG линейно зависим тогда и только тогда, когда X содержит цикл. Предположим, что X содержит в себе цикл C. Если C — это петля, то тогда в X будет содержаться нулевой вектор и он будет линейно зависимым. Если же C не петля, то каждая вершина в этом цикле будет соответствовать двум ребрам C и сумма векторов по модулю 2 будет нулевым вектором. Из-за чего X будет линейно зависимым.

Теперь предположим, что X линейно зависимый. Возьмем минимальное линейно зависимое подмножество D из X (то есть такое подмножество, что удаление из него любого элемента приводит к тому, что оно будет линейно независимым). Если D будет состоять из нулевого вектора, то тогда X содержит петлю и, соответственно, цикл.

Если D не содержит нулевого вектора: так как в поле {0, 1} существует единственный ненулевой элемент — 1, то сумма векторов из D будет нулевым вектором, из-за того, что D — минимальное линейно зависимое подмножество. Из этого следует, что D содержит ребра из цикла, и если какой-то вершине инцидентно ребро из D, то существует как минимум еще одно ребро, инцидентное ей. Действительно, возьмем ребро d1 и пусть вершины v0 и v1 соответствуют этому ребру. Пусть вершине v1 инцидентно еще какое-то ребро d2. Пусть вершина v2 будет другим концом ребра d2. Продолжим этот процесс. В результате будут получены две последовательности — v0, v1, … и d1, d2, …. Так как количество вершин в D конечно, то какая-то из вершин v должна повториться. Когда это произойдет, то в D будет найден цикл. Соответственно цикл будет найден и в X.

Базы и простые циклы

Для того, чтобы перейти к решению различных задач непосредственно при помощи матроидов, следует рассмотреть еще два важных понятия из этой теории. База матроида — это максимальное независимое множество матроида (множество из I максимальной мощности).

Простой цикл матроида — это минимальное зависимое множество матроида.

Зададим два множества — множество, состоящее из всех возможных баз матроида M, обозначим его BM, и множество, состоящее из всех возможных простых циклов матроида M, обозначим его CM. Так как матроиды обладают свойством наследственности, любое из этих двух множеств может полностью определить матроид.


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


Читайте в этой же книге: Исторический обзор | Формализация понятия алгоритма | Теорема |
<== предыдущая страница | следующая страница ==>
Шаг алгоритма| Теорема

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