http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Geork&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T08:47:55ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D0%BE%D1%80&diff=8449Бор2011-05-07T12:18:28Z<p>Geork: </p>
<hr />
<div>{{В разработке}}<br />
<br />
'''Бор''' (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на ребрах. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины. Размер бора линейно<br />
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.<br />
<br />
==Пример==<br />
Бор для набора образцов {he, she, his, hers}:<br /><br />
[[Файл:Aho-corasick1.jpg]]<br />
<br />
==Построение==<br />
===Идея===<br />
Пусть <tex>P = \{P_1,...,P_k\} </tex> — набор строк, называемый словарем.<br />
<br />
Пусть <tex>n = \sum_{i=1}^k|P_i|</tex>.<br />
<br />
Начинаем с дерева из одной вершины (корня); добавляем шаблоны <tex>P_i</tex> один за другим:<br />
Следуем из корня по ребрам, отмеченным буквами из <tex>P_i</tex>, пока возможно.<br />
<br />
Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex>.<br />
<br />
Если ребра, отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.<br />
<br />
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.<br />
===Пример реализации===<br />
<br />
==Поиск строки в бору==<br />
Поиск строки <tex>S</tex> в бору: начинаем в корне, идем по ребрам, отмеченным символами <tex>S</tex>, пока возможно.<br />
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.<br />
Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет.<br />
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.<br />
<br />
==Сжатый бор==<br />
Сжатый бор — структура данных для хранения набора строк, отличающаяся от бора<br />
следующим улучшением: если у некоторой вершины исходящая степень равна 1, то эту<br />
вершину, ребро, входящее в нее, и ребро, исходящее из нее, можно объединить в одно<br />
ребро с более чем одним символом.</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D0%BE%D1%80&diff=8448Бор2011-05-07T12:04:24Z<p>Geork: Новая страница: «'''Бор''' (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, предста…»</p>
<hr />
<div>'''Бор''' (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на ребрах. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины. Размер бора линейно<br />
зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.<br />
<br />
==Пример бора==<br />
Бор для набора образцов {he, she, his, hers}:<br /><br />
[[Файл:Aho-corasick1.jpg]]<br />
<br />
==Построение бора==<br />
Пусть <tex>P = \{P_1,...,P_k\} </tex> — набор строк, называемый словарем.<br />
<br />
Пусть <tex>n = \sum_{i=1}^k|P_i|</tex>.<br />
<br />
Начинаем с дерева из одной вершины (корня); добавляем шаблоны <tex>P_i</tex> один за другим:<br />
Следуем из корня по ребрам, отмеченным буквами из <tex>P_i</tex>, пока возможно.<br />
<br />
Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex>.<br />
<br />
Если ребра, отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.<br />
<br />
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.<br />
<br />
==Поиск строки в бору==<br />
Поиск строки <tex>S</tex> в бору: начинаем в корне, идем по ребрам, отмеченным символами <tex>S</tex>, пока возможно.<br />
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.<br />
Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки S в словаре нет.<br />
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор - это эффективный способ хранить словарь и искать в нем слова.</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&diff=7071Обход в ширину2011-01-15T21:31:56Z<p>Geork: </p>
<hr />
<div>'''Поиск в ширину''' ('''BFS''', Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами. Например, алгоритм [[Алгоритм Прима|Прима]] поиска минимального остовного дерева или алгоритм [[Алгоритм Дейкстры|Дейкстры]] поиска кротчайшего пути из одной вершины используют идеи, сходные идеями, используемыми при поиске в ширину.<br />
<br />
==Алгоритм==<br />
<br />
===Общая идея===<br />
Пусть задан граф <tex>G = (V, E)</tex> и выделена исходная вершина <tex>s</tex>. Алгоритм поиска в ширину систематически обходит все ребра <tex>G</tex> для "открытия" всех першин, достижимых из <tex>s</tex>, вычисляя при этом расстояние (минимальное количество ребер) от <tex>s</tex> до каждой достижимой из <tex>s</tex> вершины. Кроме того, в процессе обхода строится "дерево поиска в ширину" с корнем <tex>s</tex>, содержащее все достижимые вершины. Для каждой достижимой их <tex>s</tex> вершины <tex>v</tex> путь в дереве поиска в ширину соответствует кратчайшему поти от <tex>s</tex> до <tex>v</tex> в <tex>G</tex>.<br />
<br />
Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина '''открывается''' в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если <tex>(u, v) \in E</tex> и вершина <tex>u</tex> черного цвета, то вершина <tex>v</tex> либо серая, либо черная, т.е. все вершины, смежные с ней уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.<br />
<br />
Поиск в ширину стоит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина <tex>s</tex>. Если в процессе сканирования списка смежности уже открытое вершины <tex>u</tex> открывается белая вершина <tex>v</tex>, то вершина <tex>v</tex> и ребро <tex>(u, v)</tex> добавляются в дерево. При этом <tex>u</tex> является '''предшественником''' (predecessor), или '''родителем''' (parent), <tex>v</tex> в дереве поиска вширь. Посколько вершина модет быть открыта не более одного раза, она имеет не более одного родителя. <br />
<br />
=== Реализация===<br />
Приведенная ниже процедура поиска в ширину '''BFS''' предполагает, что входной граф <tex>G = (V, E)</tex> представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины <tex>u \in V</tex> хранится в переменной <tex>color[u]</tex>, а предшественник — в переменной <tex>p[u]</tex>. Если прежшественника у <tex>u</tex> нет, то <tex>p[u] =</tex> NIL. Расстояние от <tex>s</tex> до вершины <tex>u</tex>, вычисляемое алгоритмом, хранится в поле <tex>d[u]</tex>. Алгоритм использует очередь <tex>Q</tex> для работы с множеством серых вершин.<br />
'''BFS'''(<tex>G</tex>, <tex>s</tex>)<br />
1 '''for''' (для) каждой вершины <tex>u \in V[G] - s</tex><br />
2 '''do''' <tex>color[u] \leftarrow</tex> WHITE<br />
3 <tex>d[u] \leftarrow \mathcal {1}</tex><br />
4 <tex>p[u] \leftarrow</tex> NIL<br />
5 <tex>color[s] \leftarrow</tex> GRAY<br />
6 <tex>d[s] \leftarrow</tex> 0<br />
7 <tex>p[s] \leftarrow</tex> NIL<br />
8 <tex>Q \leftarrow</tex> Ø<br />
9 ENQUEUE(<tex>Q</tex>, <tex>s</tex>)<br />
10 '''while''' <tex>Q \ne </tex>Ø<br />
11 '''do''' <tex>u \leftarrow</tex> DEQUEUE(<tex>Q</tex>)<br />
12 '''for''' (для) каждой <tex>м \in Adj[u]</tex><br />
13 '''do''' '''if''' <tex>color[u] =</tex> WHITE<br />
14 '''then''' <tex>color[v] \leftarrow</tex> GRAY<br />
15 <tex>d[v] \leftarrow d[u] + 1</tex><br />
16 <tex>p[v] \leftarrow u</tex> <br />
17 ENQUEUE(<tex>Q</tex>, <tex>v</tex>)<br />
18 <tex>color[u] \leftarrow</tex>BLACK<br />
<br />
== Анализ ==<br />
Оценим время работы для входного графа <tex>G = (V, E)</tex>. После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex>O(1)</tex> времени, так что общее время операций с очередью составляет <tex>O(V)</tex>. Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна <tex> \Theta (E) </tex>, общее время, необходимое для сканирования списков, равно <tex>O(E)</tex>. Накладные расходы на инициализацию равны <tex>O(V)</tex>, так что общее время работы процедуры '''BFS''' составляет <tex>O(V + E)</tex>. Таким образом, время работы поиска в ширину линейно зависит от размера представления графа <tex>G</tex> с использованием списков смежности.<br />
<br />
== Литература ==<br />
*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%85%D0%BE%D0%B4_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83&diff=6146Обход в ширину2010-12-22T12:16:11Z<p>Geork: Новая страница: «'''Поиск в ширину''' ('''BFS''', Breadth-first search) — метод обхода и разметки вершин графа. ==Алгоритм== ==…»</p>
<hr />
<div>'''Поиск в ширину''' ('''BFS''', Breadth-first search) — метод обхода и разметки вершин графа.<br />
<br />
==Алгоритм==<br />
<br />
===Общая идея===<br />
Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем, пока очередь не пуста, будем извлекать первый элемент из очереди и добавлять в конец все не посещенные смежные с ним вершины. <br />
<br />
=== Реализация===<br />
Входные данные:<br />
vector < vector<int> > g; // граф, реализованный с помощью списка смежности<br />
int n; // число вершин<br />
int s; // стартовая вершина (вершины везде нумеруются с нуля)<br />
// чтение графа<br />
...<br />
<br />
Сам обход:<br />
queue<int> q;<br />
q.push (s);<br />
vector<bool> used (n);<br />
used[s] = true;<br />
while (!q.empty()) {<br />
int v = q.front();<br />
q.pop();<br />
for (size_t i=0; i<g[v].size(); ++i) {<br />
int to = g[v][i];<br />
if (!used[to]) {<br />
used[to] = true;<br />
q.push (to);<br />
}<br />
}<br />
}<br />
== Практические применения ==<br />
* Волновой алгоритм в трассировке печатных плат;<br />
* Поиск увеличивающего пути в Форда-Фалкерсона алгоритм|алгоритме Форда-Фалкерсон (алгоритм Эдмондса-Карпа)<br />
<br />
== Литература ==<br />
* Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 215-218. — ISBN 0-201-74395-7<br />
*Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=4013Дерево, эквивалентные определения2010-10-15T00:56:07Z<p>Geork: /* Теорема */</p>
<hr />
<div>== Определения ==<br />
{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
==Теорема==<br />
{{Теорема<br />
|statement=<br />
Для графа <tex>G</tex> с <tex>p</tex> вершинами и <tex>q</tex> ребрами следующие утверждения эквивалентны:<br />
1) <tex>G</tex> - дерево;<br />
<br />
2) любые две вершины в <tex>G</tex> соединены единственной простой цепью;<br />
<br />
3) <tex>G</tex> связный граф и <tex>p = q + 1</tex>;<br />
<br />
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;<br />
<br />
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.<br />
|proof= <br />
Для примера докажем эквивалентность первых четырёх утверждений.<br />
<br />
1) <tex> \to </tex> 2) Поскольку <tex>G</tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепи, соединяющие вершины <tex>u</tex> и <tex>v</tex>, и пусть <tex>w</tex> - первая вершина, принадлежащая <tex>P_1</tex> (при переходе по <tex>P_1</tex> из <tex>u</tex> в <tex>v</tex>), такая, что <tex>w</tex> принадлежит и <tex>P_1</tex> и <tex>P_2</tex>, но вершина, предшествующая ей в <tex>P_1</tex>, не принадлежит <tex>P_2</tex>.Если <tex>w'</tex> - следующая за <tex>w</tex> вершина в <tex>P_1</tex>, принадлежащая также <tex>P_2</tex>, то сегменты (части) цепей <tex>P_1</tex> и <tex>P_2</tex>, находящиеся между вершинами <tex>w</tex> и <tex>w'</tex>, образуют простой цикл в графе <tex>G</tex>. Поэтому если <tex>G</tex> - ациклический граф, то между любыми двумя его вершинами существует самое большое одна цепь.<br />
2) <tex> \to </tex> 3) Ясно, что граф <tex>G</tex> - связный. Соотношение <tex>p = q + 1</tex> докажем по индукции. Утверждение очевидно для связных графов с одной и двумя вершинами. Предположим, что оно верно для графов, имеющих меньше <tex>p</tex> вершин. Если же граф <tex>G</tex> имеет <tex>p</tex> вершин, то удаление из него любого ребра делает его несвязным, в силу единственности простых цепей; более того, получаемый граф будет иметь в точности две компоненты. По предположению индукции в каждой компоненте число вершин на единицу больше числа ребер. Таким образом, общее число ребер в графе <tex>G</tex> должно равняться <tex>p-1</tex>.<br />
}}<br />
<br />
'''Следствие:'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.<br />
<br />
==Литература==<br />
<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3891Дерево, эквивалентные определения2010-10-13T21:16:55Z<p>Geork: </p>
<hr />
<div>== Определения ==<br />
{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
==Теорема==<br />
{{Теорема<br />
|statement=<br />
Для графа <tex>G</tex> с <tex>p</tex> вершинами и <tex>q</tex> ребрами следующие утверждения эквивалентны:<br />
1) <tex>G</tex> - дерево;<br />
<br />
2) любые две вершины в <tex>G</tex> соединены единственной простой цепью;<br />
<br />
3) <tex>G</tex> связный граф и <tex>p = q + 1</tex>;<br />
<br />
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;<br />
<br />
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.<br />
|proof= <br />
Для примера докажем эквивалентность первых четырёх утверждений.<br />
1) <tex> \to </tex> 2) Поскольку <tex>G</tex> связный граф, то любые две его вершины соединены простой цепью. Пусть <tex>P_1</tex> и <tex>P_2</tex> - две различные простые цепи, соединяющие вершины <tex>u</tex> и <tex>v</tex>, и пусть <tex>w</tex> - первая вершина, принадлежащая <tex>P_1</tex> (при переходе по <tex>P_1</tex> из <tex>u</tex> в <tex>v</tex>), такая, что <tex>w</tex> принадлежит и <tex>P_1</tex> и <tex>P_2</tex>, но вершина, предшествующая ей в <tex>P_1</tex>, не принадлежит <tex>P_2</tex>.<br />
<br />
}}<br />
<br />
'''Следствие:'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.<br />
<br />
==Литература==<br />
<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3886Дерево, эквивалентные определения2010-10-13T21:06:20Z<p>Geork: </p>
<hr />
<div>== Определения ==<br />
{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
==Теорема==<br />
{{Теорема<br />
|statement=<br />
Для графа <tex>G</tex> с <tex>p</tex> вершинами и <tex>q</tex> ребрами следующие утверждения эквивалентны:<br />
1) <tex>G</tex> - дерево;<br />
<br />
2) любые две вершины в <tex>G</tex> соединены единственной простой цепью;<br />
<br />
3) <tex>G</tex> связный граф и <tex>p = q + 1</tex>;<br />
<br />
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;<br />
<br />
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.<br />
|proof= <br />
<br />
}}<br />
<br />
'''Следствие:'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.<br />
<br />
==Литература==<br />
<br />
* Харари Фрэнк '''Теория графов''' = Graph theory/Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3865Дерево, эквивалентные определения2010-10-13T20:45:06Z<p>Geork: </p>
<hr />
<div>{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
{{Теорема<br />
|statement=<br />
Для графа <tex>G</tex> с <tex>p</tex> вершинами и <tex>q</tex> ребрами следующие утверждения эквивалентны:<br />
1) <tex>G</tex> - дерево;<br />
<br />
2) любые две вершины в <tex>G</tex> соединены единственной простой цепью;<br />
<br />
3) <tex>G</tex> связный граф и <tex>p = q + 1</tex>;<br />
<br />
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;<br />
<br />
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.<br />
|proof= <br />
<br />
}}<br />
<br />
'''Следствие'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3612Дерево, эквивалентные определения2010-10-11T04:06:09Z<p>Geork: </p>
<hr />
<div>{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
{{Теорема<br />
|statement=<br />
Для графа <tex>G</tex> следующие утверждения эквивалентны:<br />
1) <tex>G</tex> - дерево;<br />
<br />
2) любые две вершины в <tex>G</tex>соединены единственной простой цепью;<br />
<br />
3) <tex>G</tex> связный граф и <tex>p = q + 1</tex>;<br />
<br />
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;<br />
<br />
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.<br />
|proof= <br />
<br />
}}<br />
<br />
'''Следствие'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3605Дерево, эквивалентные определения2010-10-11T03:59:09Z<p>Geork: </p>
<hr />
<div>{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
{{Теорема<br />
|statement=<br />
Для графа <math>G</math> следующие утверждения эквивалентны:<br />
1) <math>G</math> - дерево;<br />
<br />
2) любые две вершины в <math>G</math>соединены единственной простой цепью;<br />
<br />
3) <math>G</math> связный граф и <math>p = q + 1</math>;<br />
<br />
4) <math>G</math> ациклический граф и <math>p = q + 1</math>;<br />
<br />
5) <math>G</math> - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе <math>G + x</math> будет точно один простой цикл;<br />
<br />
6) G - связный граф, отличный от K<sub>p</sub> для p <tex>\ge</tex> 3, и если любую пару несмежных вершин соединить ребром х, то в графе G + x будет точно один простой цикл;<br />
<br />
7) G - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, p = q + 1, и если любую пару несмежных вершин соединить ребром x, то в графе G + x будет точно один простой цикл.<br />
|proof= <br />
<br />
}}<br />
<br />
'''Следствие'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3603Дерево, эквивалентные определения2010-10-11T03:57:44Z<p>Geork: </p>
<hr />
<div>{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
{{Теорема<br />
|statement=<br />
Для графа <tex>G</tex> следующие утверждения эквивалентны:<br />
1) <tex>G</tex> - дерево;<br />
<br />
2) любые две вершины в <tex>G</tex> соединены единственной простой цепью;<br />
<br />
3) <tex>G</tex> связный граф и <tex>p = q + 1</tex>;<br />
<br />
4) <tex>G</tex> ациклический граф и <tex>p = q + 1</tex>;<br />
<br />
5) <tex>G</tex> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для <tex>p \ge 3</tex>, и если любую пару несмежных вершин соединить ребром <tex>х</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;<br />
<br />
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.Б.<br />
|proof= <br />
<br />
}}<br />
<br />
'''Следствие'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.</div>Georkhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE,_%D1%8D%D0%BA%D0%B2%D0%B8%D0%B2%D0%B0%D0%BB%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B5_%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F&diff=3601Дерево, эквивалентные определения2010-10-11T03:35:24Z<p>Geork: Новая страница: «{{Определение |definition = Ациклический граф - граф, в котором нет циклов. }} {{Определение |definition =…»</p>
<hr />
<div>{{Определение<br />
|definition =<br />
Ациклический граф - граф, в котором нет циклов.<br />
}}<br />
{{Определение<br />
|definition =<br />
Дерево - это связный ациклический граф.<br />
}}<br />
{{Определение<br />
|definition =<br />
Граф, не содержащий циклов, называется лесом. <br />
}}<br />
{{Теорема<br />
|statement=<br />
Для графа <math>G</math> следующие утверждения эквивалентны:<br />
1) <math>G</math> - дерево;<br />
<br />
2) любые две вершины в <math>G</math>соединены единственной простой цепью;<br />
<br />
3) <math>G</math> связный граф и <math>p = q + 1</math>;<br />
<br />
4) <math>G</math> ациклический граф и <math>p = q + 1</math>;<br />
<br />
5) <math>G</math> - ациклический граф, и если любую праву несмежных вершин соединить ребром x, то в графе <math>G + x</math> будет точно один простой цикл;<br />
<br />
6) G - связный граф, отличный от K<sub>p</sub> для p <tex>\ge</tex> 3, и если любую пару несмежных вершин соеденить ребром х, то в графе G + x будет точно один простой цикл;<br />
<br />
7) G - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, p = q + 1, и если любую пару несмежных вершин соединить ребром x, то в графе G + x будет точно один простой цикл.<br />
|proof= <br />
<br />
}}<br />
<br />
'''Следствие'''<br />
<br />
В любом нетривиальном дереве имеется по крайней мере две висячие вершины.</div>Geork