Как найти число ребер полного графа - Сайт, где вы сможете решить свои вопросы

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 4 января 2021 года; проверки требуют 15 правок.

Полный граф
K₇, полный граф с 7 вершинами
Вершин	`n`
Рёбер	${frac {n(n-1)}{2}}$
Диаметр	${displaystyle left{{begin{array}{ll}0&nleq 1\1&{text{иначе}}end{array}}right.}$
Обхват	${displaystyle left{{begin{array}{ll}infty &nleq 2\3&{text{иначе}}end{array}}right.}$
Автоморфизмы	n! (S_n)
Хроматическое число	`n`
Хроматический индекс	`n` если `n` – нечётное, иначе n − 1
Спектр	${displaystyle left{{begin{array}{lll}emptyset &n=0\left{0^{1}right}&n=1\left{(n-1)^{1},-1^{n-1}right}&{text{иначе}}end{array}}right.}$
Свойства	(n − 1)-регулярный граф Симметричный граф Вершинно-транзитивный граф Рёберно-транзитивный граф Сильно регулярный граф Целый граф Гамильтонов граф
Обозначение	K_n
Медиафайлы на Викискладе

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.^[1] По́лный ориенти́рованный граф — ориентированный граф, в котором каждая пара различных вершин соединена парой ребер с противоположными ориентациями.^[2]
Принято считать, что теория графов берет свое начало с решения Леонардом Эйлером задачи о семи кёнигсбергских мостах, датированного 1736 годом, однако изображения полных графов, вершины которых располагаются в вершинах правильных многоугольников, встречаются ещё в 13 веке, в работе Раймунда Луллия.^[3]
Подобные рисунки иногда называют мистическими розами.^[4]

Обычно полный граф с вершинами обозначается через K_n . Некоторые источники утверждают, что буква в этом обозначении является сокращением от немецкого слова нем. komplett,^[5] в переводе на русский – «полный, целый», однако оригинальное название полного графа на немецком, нем. vollständiger Graph, не содержит буквы . По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.^[6]

Комбинаторные свойства[править | править код]

Любой полный граф является своей максимальной кликой.

Дополнение графа – это пустой граф, то есть граф без рёбер.

Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.

В полном графе не может быть независимого множества более чем из одной вершины.^[7]

Индексы Хосойи (полные числа паросочетаний) полного графа являются телефонными числами^[en] (-ое телефонное число – это число различных вариантов, которыми из человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причем на полных графах реализуются максимально возможные значения индекса Хосойи для -вершинного графа.^[10] Эти индексы образуют последовательность

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, … последовательность A000085 в OEIS.

Теорема Турана: Обозначим через максимальное количество рёбер, которое может иметь граф с вершинами, не содержащий подграфа, изоморфного . Тогда, если , где — остаток от деления на , то этот максимум равен ${displaystyle {textrm {ex}}(v,n)={frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{frac {r(r-1)}{2}}.}$ Среди всех графов на вершинах, не содержащих подграфа , этот максимум по количеству рёбер достигается на графе $T_{n}(v)$ , определяемом следующим образом. Пусть $T_{n}(v)$ это граф с вершинами, разобьём все вершины на «почти равных» групп (то есть возьмём групп по вершине и групп по вершин, если с остатком ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим -дольный граф.^[13]

Геометрические и топологические свойства[править | править код]

Число пересечений[править | править код]

Известна верхняя оценка на число пересечений полного графа, а именно ${displaystyle {textrm {cr}}(K_{n})leq {tfrac {1}{4}}leftlfloor {tfrac {n}{2}}rightrfloor leftlfloor {tfrac {n-1}{2}}rightrfloor leftlfloor {tfrac {n-2}{2}}rightrfloor leftlfloor {tfrac {n-3}{2}}rightrfloor }$ . Впервые, в конце пятидесятых, вопрос о существовании такой оценки выдвинул Энтони Хилл,^[15] известный британский художник-абстракционист. Ему удалось разработать несколько особых методов изображения полных графов, позволивших в дальнейшем эффективно исследовать их числа пересечений. Один из таких методов известен как «рисунок на алюминиевой банке», а другой – как «изображения Харари-Хилла».^[16] Анализируя эти методы изображения математикам Блажеку и Коману удалось подтвердить^[17] оценку Хилла для всех полных графов в 1964 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно ${displaystyle {textrm {cr}}(K_{n})={tfrac {1}{4}}leftlfloor {tfrac {n}{2}}rightrfloor leftlfloor {tfrac {n-1}{2}}rightrfloor leftlfloor {tfrac {n-2}{2}}rightrfloor leftlfloor {tfrac {n-3}{2}}rightrfloor }$ . Эта гипотеза известна как гипотеза Хилла и на данный момент подтверждена только для нескольких малых .^[18] Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работе^[19] за 1960 год содержатся прямые намеки на данный вопрос, или гипотезой Харари-Хилла, так как работа^[20] Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы.^[21]
Полные графы K_n при nle 4 являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал,^[22] что гипотеза Хилла верна для всех , а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердили^[23] гипотезу Хилла для . В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили,^[24] что ${displaystyle {textrm {cr}}(K_{13})}$ является нечетным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

	$K_{5}$	$K_{6}$	${displaystyle K_{7}}$	$K_{8}$	${displaystyle K_{9}}$	${displaystyle K_{10}}$	${displaystyle K_{11}}$	${displaystyle K_{12}}$	$K_{13}$
									или

Кроме того, в 1969 году Гай получил^[25] нижнюю оценку на число пересечений полного графа, а именно
${displaystyle {textrm {cr}}(K_{n})geq {tfrac {1}{120}}n(n-1)(n-2)(n-3)}$ . При этом, ещё в 1960 году он обнаружил,^[19] что существует предел ${displaystyle lim _{nto infty }{{textrm {cr}}(K_{n})/Z(n)}}$ , где ${displaystyle Z(n)={tfrac {1}{4}}leftlfloor {tfrac {n}{2}}rightrfloor leftlfloor {tfrac {n-1}{2}}rightrfloor leftlfloor {tfrac {n-2}{2}}rightrfloor leftlfloor {tfrac {n-3}{2}}rightrfloor }$ , а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили,^[26] что верна оценка

${displaystyle lim _{nto infty }{frac {{textrm {cr}}(K_{n})}{Z(n)}}geq 0.8594}$

Число прямолинейных пересечений[править | править код]

Для и n=9 число прямолинейных пересечений графа K_n , которое обычно обозначается через ${displaystyle {textrm {rcr}}(K_{n})}$ , совпадает с его обыкновенным числом пересечений. Однако, число прямолинейных пересечений графа $K_{8}$ равно , тогда как ${displaystyle {textrm {cr}}(K_{8})=18}$ .^[20] В 2001 году Алекс Бродский, Стефан Дуроше и Эллен Гетнер^[en] выяснили,^[27] что число прямолинейных пересечений графа ${displaystyle K_{10}}$ равно 62, при ${displaystyle {textrm {cr}}(K_{10})=60}$ .
На данный момент точные значения ${displaystyle {textrm {rcr}}(K_{n})}$ известны для и . Суть точного вычисления заключается в нахождении соответствующих (и совпадающих) нижних и верхних оценок. Нижние оценки для были построены^[28] совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром в 2012 году, нижняя оценка для построена^[29] совместно математиками Марио Сетина, Сесаром Эрнандес-Велесом, Хесусом Леаньосом и Кристобалем Вильялобос Гильеном в 2012 году, а все верхние оценки получены австрийским математиком Освином Айххольцером^[30]. Кроме того, Айххольцер опубликовал^[30] на своем сайте суммарную информацию обо всех известных на данный момент нижних и верхних оценках на ${displaystyle {textrm {rcr}}(K_{n})}$ вплоть до . Ниже приведена таблица с соответствующими оценками для .

$K_{5}$

$K_{6}$

${displaystyle K_{7}}$

$K_{8}$

${displaystyle K_{9}}$

${displaystyle K_{10}}$

${displaystyle K_{11}}$

${displaystyle K_{12}}$

$K_{13}$

${displaystyle K_{14}}$

${displaystyle K_{15}}$

${displaystyle K_{16}}$

${displaystyle K_{17}}$

${displaystyle K_{18}}$

${displaystyle K_{19}}$

${displaystyle K_{20}}$

${displaystyle K_{21}}$

${displaystyle K_{22}}$

${displaystyle K_{23}}$

${displaystyle K_{24}}$

${displaystyle K_{25}}$

${displaystyle K_{26}}$

${displaystyle K_{27}}$

${displaystyle K_{28}}$

${displaystyle K_{29}}$

${displaystyle K_{30}}$

или

, или

В 1994 году Эдвард Р. Шайнерман^[en] и Герберт С. Уилф^[en] обнаружили^[31] неожиданную связь между числом прямолинейных пересечений графа K_n и задачей Сильвестра “о четырех точках” из вероятностной геометрии.^[32] Пусть — открытое множество на плоскости с конечной мерой Лебега. Обозначим через вероятность того, что если в равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырехугольником, а через ${displaystyle {textrm {q}}^{*}}$ – инфимум значений по всем таким . Тогда верно равенство

${displaystyle lim _{nto infty }{frac {{textrm {rcr}}(K_{n})}{n choose 4}}={textrm {q}}^{*},}$

где обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялись^[33] верхняя и нижняя оценки на константу ${displaystyle {textrm {q}}^{*}}$ , и на данный момент лучшая нижняя^[34] и лучшая верхняя^[28] оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

${displaystyle 0.379972<{frac {277}{729}}leq {textrm {q}}^{*}leq {frac {83247328}{218791125}}<0.380488.}$

Книжное вложение с тремя страницами для графа $K_{5}$

Планарность и книжная толщина[править | править код]

Графы с K_1 по $K_{4}$ являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф $K_{5}$ и, следовательно, не удовлетворяют критерию Понтрягина — Куратовского.^[35]

При граф K_n является 1-планарным графом, но при граф K_n не является 1-планарным.^[36]

Книжная толщина графа $K_{5}$ равна . Для любых ngeq 4 граф K_n имеет книжную толщину в точности .^[37]

Симплексы и многогранники[править | править код]

Полный граф образуется из вершин и ребер (n-1)-симплекса. Так, например, геометрически $K_{3}$ образует множество вершин и ребер треугольника, $K_{4}$ – тетраэдра и так далее. Объединение всех семи вершин и двадцати одного ребра многогранника Часара, топологически эквивалентного тору, образует полный граф ${displaystyle K_{7}}$ .

Граф 2-смежностного многогранника является полным графом.

Зацепленность и заузленность[править | править код]

Граф $K_{6}$ не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Кэмерон Гордон^[en] в 1983 году, для любого вложения $K_{6}$ в трехмерное пространство существует два таких цикла в $K_{6}$ , образы которых при вложении имеют нечетный коэффициент зацепления.^[38] А для любого вложения графа ${displaystyle K_{7}}$ в трехмерное пространство существует такой гамильтонов цикл в ${displaystyle K_{7}}$ , образ которого при вложении имеет нетривиальный инвариант Арфа^[en], то есть является нетривиальным узлом.^[38] В 2002 году Эрика Флапан^[en] доказала, что для любого найдется такое , что каждое вложение графа K_n в $mathbb {R} ^{3}$ содержит двукомпонентое зацепление, коэффициент зацепления которого равен .^[39] А кроме того, для любого найдется такое , что каждое вложение графа K_n в $mathbb {R} ^{3}$ содержит узел , такой что ${displaystyle |a_{2}(Q)|geq m}$ , где через ${displaystyle a_{2}(Q)}$ обозначен второй коэффициент многочлена Конвея узла .^[39]

Примеры[править | править код]

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.

K₁ (0)	K₂ (1)	K₃ (3)	K₄ (6)	K₅ (10)	K₆ (15)

K₇ (21)	K₈ (28)	K₉ (36)	K₁₀ (45)	K₁₁ (55)	K₁₂ (66)

Примечания[править | править код]

↑ Карпов Дмитрий Валерьевич, 2022, p. 17.
↑ Bang-Jensen, Gutin, 2018, p. 17.
↑ Donald E. Knuth, 2015.
↑
Mystic Rose (англ.). nrich.maths.org. Дата обращения: 22 января 2023.
↑ Gries, Schneider, 1993.
↑ Thomas L. Pirnot, 2000, p. 154.
↑ Карпов Дмитрий Валерьевич, 2022, p. 374.
↑ Joos, Kim, Kuhn, Osthus, 2019.
↑ Mehdi Hassani, 2004.
↑ Tichy, Wagner, 2005.
↑ David Callan, 2009.
↑ Frank P. Ramsey, 1930.
↑ Карпов Дмитрий Валерьевич, 2022, p. 494.
↑ Карпов Дмитрий Валерьевич, 2022, p. 424.
↑ Beineke, Wilson, 2010, p. 43.
↑ Marcus Schaefer, 2018.
↑ Blažek, Koman, 1964.
↑ Marcus Schaefer, 2018, p. 25.
↑ ¹ ² Richard K. Guy, 1960.
↑ ¹ ² Harary, Hill, 1963.
↑ Marcus Schaefer, 2018, 1.3 Hill and the Crossing Number of Complete Graphs, p. 25: «the first
explicit statement in print seems to be in a paper by Harary and Hill».
↑ Richard K. Guy, 1972.
↑ Pan, Richter, 2007.
↑ McQuillan, Pan, Richter, 2015.
↑ Richard K. Guy, 1969.
↑ Klerk, Pasechnik, Schrijver, 2007.
↑ Brodsky, Durocher, Gethner, 2001.
↑ ¹ ² Ábrego, Fernández-Merchant, Leaños, Salazar, 2012.
↑ Cetina, Hernández-Vélez, Leaños, Villalobos, 2012.
↑ ¹ ² Aichholzer, 2015.
↑ Scheinerman, Wilf, 1994.
↑ Eric W. Weisstein, 2004, О задаче Сильвестра.
↑ Ábrego, Fernández-Merchant, Salazar, 2013, История исследований числа прямолинейных пересечений полных графов..
↑ Ábrego, Fernández-Merchant, Leaños, Salazar, 2010.
↑ Карпов Дмитрий Валерьевич, 2022, p. 237.
↑ Карпов Дмитрий Валерьевич, 2022, p. 308.
↑ Kainen Bernhart, 1979, pp. 320–331.
↑ ¹ ² Conway, Gordon, 1983.
↑ ¹ ² Flapan, 2002.

Литература[править | править код]

Карпов Д. В. Теория графов — Москва: МЦНМО, 2022. — 560 с. — ISBN 978-5-4439-1690-3.

Ábrego B. M., Fernández-Merchant S., Salazar G. The rectilinear crossing number of : Closing in (or Are We?) (англ.) // Thirty essays on geometric graph theory / János Pach^[en]. — New York: Springer, 2013. — P. 5-18. — doi:10.1007/978-1-4614-0110-0_2.

Ábrego B. M., Fernández-Merchant S., Leaños J., Salazar G. 3-symmetric and 3-decomposable geometric drawings of (англ.) // Discrete Applied Mathematics^[en]. — 2010. — Vol. 158, iss. 12. — P. 1240-1258. — doi:10.1016/j.dam.2009.09.020.

Ábrego B. M., Fernández-Merchant S., Leaños J., Salazar G. On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of (англ.) // Discrete & Computational Geometry^[en]. — 2012. — Vol. 48, iss. 1. — P. 192-215. — doi:10.1007/s00454-012-9403-y.

Aichholzer O. On the Rectilinear Crossing Number (англ.) (26 мая 2015). Дата обращения: 22 января 2023.

Bang-Jensen J., Gutin G.^[en]. Classes of Directed Graphs (англ.) — Springer International Publishing, 2018. — 560 p. — (Springer Monographs in Mathematics). — doi:10.1007/978-3-319-71840-8_1.

Beineke L. W.^[en], Wilson R.^[en]. The early history of the brick factory problem (англ.) // The Mathematical Intelligencer^[en]. — 2010. — Vol. 32, iss. 2. — P. 41-48. — doi:10.1007/s00283-009-9120-4.

Bernhart F. R., Kainen P. C.^[en]. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 3. — С. 320–331. — doi:10.1016/0095-8956(79)90021-2.

Blažek J., Koman M. A minimal problem concerning complete plane graphs (англ.) // Miroslav Fiedler^[en] Theory of graphs and its applications. — Czech Academy of Sciences, 1964. — P. 113-117.

Brodsky A., Durocher S., Gethner E.^[en]. The rectilinear crossing number of ${displaystyle K_{10}}$ is 62 (англ.) // The Electronic Journal of Combinatorics^[en]. — 2001. — Vol. 8, iss. 1. — P. 1-30.

Callan D. A combinatorial survey of identities for the double factorial (англ.). — 2009. — Bibcode: 2009arXiv0906.1317C. — arXiv:0906.1317.

Cetina M., Hernández-Vélez C.‬, Leaños J., Guillén C. V. Point sets that minimize (≤k)-edges, 3-decomposable drawings, and the rectilinear crossing number of ${displaystyle K_{30}}$ (англ.) // Discrete Mathematics. — 2012. — Vol. 311, iss. 16. — P. 1646–1657. — doi:10.1016/j.disc.2011.03.030.

Conway J. H., Gordon C. McA^[en]. Knots and links in spatial graphs (англ.) // Journal of Graph Theory^[en]. — 1983. — Vol. 7, no. 4. — P. 445-453. — doi:10.1002/jgt.3190070410.

Erica Flapan^[en]. Intrinsic knotting and linking of complete graphs (англ.) // Algebraic & Geometric Topology^[en]. — 2002. — Vol. 2, no. 1. — P. 371-380. — doi:10.2140/agt.2002.2.371.

Gries D., Schneider F. B. A Logical Approach to Discrete Math (англ.) — Berlin: Springer, 1993. — 436 p. — ISBN 978-0387941158.

Guy R. K. A combinatorial problem (англ.) // NABLA (Bulletin of the Malaysian Mathematical Sciences Society). — 1960. — Vol. 7. — P. 68-72.

Guy R. K. The decline and fall of Zarankiewicz’s theorem (англ.) // Frank Harary Proof Techniques in Graph Theory. — New York: Academic Press, 1969. — P. 63–69.

Guy R. K. Crossing numbers of graphs (англ.) // Graph Theory and Applications. — Berlin, Heidelberg: Springer, 1972. — P. 111-124.

Harary F., Hill A. On the number of crossings in a complete graph (англ.) // Proceedings of the Edinburgh Mathematical Society. — Edinburgh, 1963. — Vol. 13, iss. 4. — P. 333-338.

Hassani M. Cycles in graphs and derangements (англ.) // The Mathematical Gazette^[en]. — 2004. — Vol. 88, iss. 511. — P. 123-126. — doi:10.1017/S0025557200174443.

Joos F., Kim J., Kuhn D., Osthus D. Optimal packings of bounded degree trees (англ.) // Journal of the European Mathematical Society. — 2019. — 8 May (vol. 21, iss. 12). — P. 3573-3647. — ISSN 1435-9855. — doi:10.4171/JEMS/909.

de Klerk E., Pasechnik D. V., Schrijver A. Reduction of symmetric semidefinite programs using the regular ∗-representation (англ.) // Mathematical Programming^[en]. — 2007. — Vol. 109, iss. 2-3, Ser. B. — P. 613-624. — doi:10.1007/s10107-006-0039-7.

Knuth D. E. Two thousand years of combinatorics // Combinatorics: Ancient & Modern (англ.) / Robin Wilson^[en], John J. Watkins. — Oxford: Oxford University Press, 2015. — P. 7–37. — 392 p. — ISBN 978-0191630620.

McQuillan D., Pan S., Richter R. B. On the crossing number of $K_{13}$ (англ.) // Journal of Combinatorial Theory, Series B. — 2015. — Vol. 115. — P. 224–235. — doi:10.1016/j.jctb.2015.06.002.

Pirnot T. L. Mathematics All Around (англ.) — Boston: Addison Wesley, 2000. — 814 p. — ISBN 978-0201308150.

Pan S., Richter B. R. The crossing number of ${displaystyle K_{11}}$ is 100 (англ.) // Journal of Graph Theory^[en]. — 2007. — Vol. 56, iss. 2. — P. 128-134. — doi:10.1002/jgt.20249.

Ramsey F. P. On a problem of formal logic (англ.) // Proceedings of the London Mathematical Society. — 1930. — Vol. 30. — P. 264—286. — doi:10.1112/plms/s2-30.1.264.

Schaefer M. Crossing numbers of graphs (англ.) — Boca Raton: CRC Press, 2018. — 376 p. — doi:10.1201/9781315152394.

Scheinerman E. R.^[en], Wilf H. S.^[en]. The rectilinear crossing number of a complete graph and Sylvester’s “four point problem” of geometric probability (англ.) // The American mathematical monthly^[en]. — 1994. — Vol. 101, iss. 10. — P. 939-943. — doi:10.2307/2975158.

Tichy R. F., Wagner S. Extremal problems for topological indices in combinatorial chemistry (англ.) // Journal of Computational Biology^[en]. — 2005. — Vol. 12, iss. 7. — P. 1004–1013. — doi:10.1089/cmb.2005.12.1004. — PMID 16201918.

Weisstein E. W. Sylvester’s Four-Point Problem (англ.) (2004). Дата обращения: 24 января 2023.

Источник

Сообщение от bambique

Откуда взята формула, которая определяет количество ребер в полном графе?

Полный граф — это такой граф, в котором каждая вершина соединена ребром со всеми остальными вершинами.
Значит, если в графе n вершин, то каждая вершина соединена с n-1 lдругими вершинами (со всеми, кроме себя).
Если в графе n вершин, каждая из которых имеет n-1 ребер, то общее количество ребер будет n(n-1).
Но каждое ребро соединяет две вершины, так что выше мы посчитали каждое ребро дважды, потому для компенсации делим на два, вот и получается n(n-1)/2

Источник

В главе 1 мы дали понятие графа. Рассмотрим
еще некоторые понятия и определения
теории графов.

Отметим, что многие понятия, рассматриваемые
в данной главе, не являются устоявшимися,
и могут в различной литературе определяться
неодинаково.

Пусть v₁,v₂,…,v_n,v_n₊₁– произвольная последовательность
вершин орграфа.

Цепьюназывается любая последовательность
дугe₁,e₂,…,e_n,
такая, что концевыми вершинами дугиe_iявляются вершиныv_iиv_i₊₁,
то естьe_i=(v_i,v_i₊₁)
илиe_i=(v_i₊₁,v_i)
дляi=1,2,…,n.

Цепь, для которой e_i=(v_i,v_i₊₁)
при всехi=1,2,…,n,
называетсяпутём.

Цикломназывается цепь, у которой
начальная и конечная вершины совпадают.

Контуромназывается путь, у которого
начальная и конечная вершины совпадают.

Цепь, путь, цикл или контур называются
простыми, если они не содержат внутри
себя циклов.

У графа, изображенного на рис. 3.1

– дуги (v₂,v₁),
(v₂,v₂),
(v₃,v₂),
(v₃,v₄)
образуют цепь, соединяющую вершинуv₁с вершинойv₄;

– дуги (v₂,v₂),
(v₂,v₄),
(v₄,v₃)
образуют путь, соединяющий вершиныv₂иv₃;

– дуги (v₃,v₂),
(v₂,v₄),
(v₃,v₄)
образуют цикл с начальной и конечной
вершинойv₃;

– дуги (v₃,v₂),
(v₂,v₄),
(v₄,v₃)
образуют контур с начальной и конечной
вершинойv₃;

– цепь (v₂,v₁),
(v₃,v₂),
(v₃,v₄),
(v₄,v₃)
с начальной вершинойv₁и конечнойv₃не
является простой, так как содержит
внутри себя цикл (v₃,v₄),
(v₄,v₃).

Граф называется связным, если в нем
для каждой пары вершин найдётся
соединяющая их цепь.

Связный и несвязный граф представлен
на рис.3.2.

Любой граф можно рассматривать как
некоторую совокупность связных графов.
Каждый из этих графов называется
компонентомисходного графа.

Несвязный граф, изображённый на рис.
3.2, имеет два компонента.

Множество дуг, исключение которых из
графа увеличивает число его компонентов,
называется разрезом.

Для связного графа, изображенного на
рис. 3.2, разрезом является выделенная
дуга e, так как её
удаление увеличивает число компонентов
до двух.

Пусть G=(V,E),VV,тогда граф, множество вершин которого
совпадает сV,
а множество дуг включает все дуги
множестваEс концевыми
вершинами вV,
называетсяподграфом графаG,порождённым V.

Пусть EE,
тогда граф, для которого множество дуг
совпадает сE,
а множество вершин включает вершины,
инцидентные дугам изE,
называетсяподграфом графаG,порождённым E.

Граф называется полным, если
любые две его вершины смежные.

Граф Gназываетсяпустым, если в нём нет рёбер.

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

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

Если рёбра, составляющие дерево, заменить
ориентированными дугами, то получим
ориентированное дерево. Если из
контекста ясно, о каком дереве идет
речь, то в дальнейшем слово «ориентированное»
будем опускать.

Для
ориентированного дерева имеет смысл
ввести понятие корня.
Минимальное по мощности множество
вершин ориентированного дерева, из
которых существуют пути во все оставшиеся
вершины, будем называть множеством
корней.

Покрывающим (остовным) деревомграфаG называется
дерево, являющееся подграфом графаGи содержащее все его вершины.

Если граф Gнесвязен, то
множество, состоящее из основных деревьев
каждой компоненты, называетсяпокрывающим
(остовным) лесом.

Обобщением графа является гиперграф.

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

Подобные объекты в математике известны
давно, однако введение термина “гиперграф”
связано с успешным рассмотрением на
них ряда важных понятий и методов теории
графов.

Упражнения:

1.Определить число рёбер в полном графе
порядка n. Нарисовать
примеры полных графов порядка 2, 3, 4, 5.

2.Определить число рёбер в покрывающем
дереве графа порядка n.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Введение. Теория множеств

Понятие множества
Способы задания множеств
Операции над множествами: объединение, пересечение, разность, декартово произведение.

Часть I Комбинаторика

1. Основные правила комбинаторики

Правило суммы
Правило произведения

2. Перестановка. Факториал

3. Классические задачи комбинаторики

Размещения различных предметов по различным ящикам с различными ограничениями
Раскраски различных предметов с различными ограничениями
Количество слов фиксированной длины в заданном алфавите с различными ограничениями

4. Выборки

Упорядоченные выборки
Неупорядоченные выборки, число сочетаний (формула с доказательством)
Количество подмножеств фиксированной мощности

5. Бином Ньютона. Биномиальные коэффициенты. Полиномиальные коэффициенты.

6. Вычисление сумм точное и приближенное

7. Оценка сложности фрагментов программы

Часть II Теория графов

1. Основные определения

Определение графа
Ориентированные и неориентированные графы
Геометрическая интерпретация графа
Кратные ребра и петли. Простой граф
Понятия смежности и инцидентности
Степень вершины. Теорема о сумме степеней вершин графа, лемма о рукопожатиях
Полный граф. Количество ребер в полном графе

2. Способы задания графов

Матрицы инциденций неориентированных графов
Матрицы инциденций ориентированных графов
Матрицы смежности графов

3. Связность графов

Подграф
Пути и циклы в графе. Связность неориентированных графов
Компонента связности неориентированного графа

4. Деревья

Определение дерева, свойства дерева
Остовное дерево графа

Часть III Задачи на графах и алгоритмы их решения

Задача поиска в графах

Алгоритм поиска в глубину
Алгоритм поиска в ширину
Задачи, которые можно решать с использованием модифицированных алгоритмов поиска

Взвешенные графы

Определение взвешенного графа. Вес графа. Матрица весов.
Алгоритм Краскала
Алгоритм Прима

Задача о кратчайшем пути в сети

Постановка задачи, особенности графов, для которых такую задачу можно формулировать
Алгоритм Форда-Беллмана. Дерево кратчайших путей.

Эйлеровы пути и циклы

Определение эйлерова пути, эйлерова цикла, эйлерова графа
Критерий существования эйлерова цикла (пути) в графе)
Алгоритм построения эйлерова цикла в эйлеровом графе

Гамильтоновы пути и циклы

Определение гамильтонова пути, гамильтонова цикла
Оценка количества гамильтоновых циклов п полном графе
Переборный алгоритм нахождения гамильтонова пути в графе, либо доказательства отсутствия ГЦ

Задача коммивояжера

Постановка задачи
Эвристические алгоритмы решения задачи коммивояжера

Связность ориентированных графов: слабая связность, односторонняя достижимость, сильная связность

Теория множеств

Понятие множества

Множество (S) – любое собрание определённых и различимых между собой объектов нашей интуиции, мыслимое, как единое целое.

Элементы множества – объекты, составляющие множество (числа, функции, множества внутри множеств).

Универсальное множество (U, универсум) – множество, содержащие в себе все другие возможные объекты.

Пустое множество (Ø) – множество, не содержащее в себе элементов

Парадокс: если универсум содержит все множества и сам является объектом, то он должен содержать сам себя.

Обозначения:

𝑥 ∈ 𝐴 – объект x принадлежит множеству А
𝑥 ∉ 𝐴 – объект x не принадлежит множеству А
𝐴 = 𝐵 – множество А равно множеству В, то есть А состоит ровно из тех же элементов, что и В

Способы задания множества

Перечисление: 𝐴 = {𝑎, 𝑏, 𝑐} – a,b,c являются элементами множества, и только они
- При перечислении элементов множества порядок их перечисления не важен: {𝑎,𝑏, 𝑐} = {𝑏, 𝑐, 𝑎} = {𝑐,𝑎, 𝑏}
- Перечисление невозможно, если:
  - Рассматриваемое множество состоит из элементов, которые нельзя указать по какой-то причине
  - Множество содержит бесконечное число элементов
  - Множество содержит слишком большое число элементов
Указание свойства: 𝐵 = {𝑥: 𝑥 − чётное число} – B является множеством чётных чисел.
Способ сопоставим с предикатом P(x), принимающим значения «ИСТИНА-ЛОЖЬ»
Комбинированный:
- С неполным перечислением: 𝐸 = {𝑒1, 𝑒2, … , 𝑒𝑛}
- Буквенные обозначения:
  - ℕ − множество натуральных чисел
  - ℤ − множество целых чисел
  - ℚ − множество рациональных чисел
  - ℝ − множество действительных чисел
  - ℂ − множество комплексных чисел

Операции над множествами

Дополнение: 𝐵 = 𝐴̅
Объединение: 𝐶 = 𝐴 ∪ 𝐵
Пересечение: 𝐷 = 𝐴 ∩ 𝐵
Разность: 𝐸 = 𝐴𝐵 = 𝐴 ∩ 𝐵
Симметрическая разность: 𝐹 = 𝐴Δ𝐵 = 𝐵Δ𝐴 = (𝐴 ∪ 𝐵)(𝐵 ∪ 𝐴)
Декартово произведение: 𝐴 = {𝑎, 𝑏, 𝑐} } ⇒ 𝐹 = 𝐴 × 𝐵 = 𝐵 = {1,2}

Декартов квадрат: 𝐵 × 𝐵 = 𝐵2

Комбинаторика

Основные правила комбинаторики

Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.

Основные задачи комбинаторики:

Исследование задачи существования данной конфигурации
Подсчёт числа конфигураций
Приближённый подсчёт числа конфигураций
Перечисление конфигураций
Оптимизация
Конструирование и анализ комбинаторных алгоритмов

Правило суммы

Если объект А может быть выбран m способами, а объект В – n способами, то при условии,
что одновременный выбор А и В невозможен, выбор «А или В» можно осуществить m + n способами

Пример: на собрании присутствуют 10 мужчин и 15 женщин.
Чтобы выбрать кого-то одного председателем, существует 10 + 15 = 25 способов выбора.

Правило произведения

Если объект A может быть выбран m способами, и после каждого такого выбора объект B
в свою очередь может быть выбран n способами,
то выбор «A и В» в указанном порядке можно осуществить m * n способами

Пример: в ресторане клиент выбирает из 10 первых блюд и из 14 вторых.

Выбрать набор, в который входят и первое, и второе, клиент может 10 * 14 = 140 способами.

Перестановка. Факториал

Факториал натурального числа – произведение всех натуральных чисел от 1 до данного.

𝑛! = 1 ∗ 2 ∗ 3 ∗ … ∗ (𝑛 − 1) ∗ 𝑛
0! = 1
(𝑛 + 1)! = 𝑛! (𝑛 + 1)

Для приближённого вычисления факториала используется формула Стирлинга: 𝑛! ≈ 𝑛𝑛𝑒−𝑛√2𝜋𝑛

Перестановка 𝑨𝒏𝒏 – упорядоченная последовательность, составленная из всех предметов из n заданных.

Две перестановки считаются разными, если они отличаются порядком элементов.

Теорема: количество перестановок п элементов равно п!
Доказательство: перестановку можно рассматривать как размещение n различных элементов по n различным ящикам при условии,
что каждый ящик содержит ровно один элемент.

Количество таких размещений равно 𝐴𝑛𝑛 = 𝑛!
Пример: Даны три элемента {1,2,3}, для них существуют следующие перестановки:
– 123
– 213
– 312
– 132
– 231
– 321

То есть 6 перестановок: 3! = 1 ∗ 2 ∗ 3 = 6

Классические задачи комбинаторики

Размещение n предметов по k ящикам: Каждый ящик может вместить k предметов. Все предметы должны быть размещены, порядок не важен. При этом могут остаться незаполненные ящики. Каждый предмет размещается в один из k ящиков независимо от других:
𝑘 ∗ 𝑘 ∗ 𝑘 ∗ … ∗ 𝑘 = 𝑘𝑛
Раскраска р предметов в r цветов: Каждый предмет может быть окрашен ровно в один цвет, краски каждого цвета хватит для окраски всех предметов. Каждый предмет красится независимо от других только в один цвет, значит, число способов перекраски равно
𝑟𝑝
Количество слов длины t в заданном алфавите длины m: На каждое из t мест символ можно выбрать т способами, таким образом количество слов равно
𝑚 ∗ 𝑚 ∗ … ∗ 𝑚 = 𝑚𝑡
Пример: существует 32 = 9 слов длины 2 в алфавите {1,2,3}:
- 11
- 12
- 13
- 21
- 22
- 23
- 31
- 32
- 33

Выборки

Выборки из n по k – k-элементные подмножества данного n-множества

Упорядоченные выборки – выборки, в которых важен порядок элементов:
{𝑎, 𝑏,𝑐} ≠ {𝑐, 𝑏, 𝑎}
Неупорядоченные выборки – выборки, в которых не важен порядок элементов:
{𝑎, 𝑏,𝑐} = {𝑐, 𝑏, 𝑎} Количество неупорядоченных выборок равно С𝑘𝑛 – числу сочетаний из n по k
Количество подмножеств фиксированной мощности: число подмножеств множества А равно 2𝑛.
С другой стороны, просуммируем количество k-элементных подмножеств при 0 ≤ 𝑘 ≤ 𝑛.

Получим равенство: С0𝑛 + С1𝑛 + ⋯ + С𝑛𝑛 = 2𝑛

Бином Ньютона. Биноминальные и полиномиальные коэффициенты

Вычисление сумм: точное и приближённое

Оценка сложности фрагмента программы

Теория графов

Основные определения

Определение графа

Пусть 𝑉={𝑣1,𝑣2,…,𝑣𝑛} – множество.

Объект вида (𝑣𝑖,𝑣𝑗)называется парой элементов множества V.

Пусть E–множество: 𝐸={𝑒1,𝑒2,…,𝑒𝑚}, элементы которого являются парами вершин: 𝑒1=(𝑣𝑖,𝑣𝑗),𝑒2=(𝑣𝑘,𝑣𝑙),𝑒3=(𝑣𝑘,𝑣𝑙),𝑒4=(𝑣𝑧,𝑣𝑧),

Пара (𝑉,𝐸) называется графом и обозначается 𝐺=(𝑉,𝐸)

Элемент множества 𝑉 называется вершиной графа.

Запись 𝑣𝑖∈𝑉 обозначает, что 𝑣𝑖 является вершиной графа 𝐺=(𝑉,𝐸).

Множество 𝑉 – множество вершин.

Элемент набора 𝐸 называется ребром графа. Запись 𝑒𝑗∈𝐸 обозначает, что 𝑒𝑗 является ребром графа 𝐺=(𝑉,𝐸). Набор 𝐸-набор ребер.

Ориентированные и неориентированные графы

Если все пары в 𝐸 неупорядоченные ((𝑢,𝑣)=(𝑣,𝑢)={𝑢,𝑣}), то граф 𝐺 называется неориентированным.

Если каждая пара в 𝐸 упорядочена ((𝑢,𝑣)≠(𝑣,𝑢)), то граф 𝐺 называется ориентированным графом, или орграфом.

Для оргафов используют обозначение G⃗=(V⃗,E⃗). Элементы E⃗ называются ориентированными ребрами, или дугами, элементы V ⃗ –узлами.

Геометрическая интерпретация графа

Геометрическая реализация (геометрическая интерпретация) – его изображение на плоскости.

Каждой вершине графа сопоставляется точка, а каждому ребру, т.е. паре вершин – непрерывная не самопересекающаяся кривая, соединяющая эти вершины.

В случае ориентированного графа на кривой указывают направление от начальной вершины дуги к конечной.

Кратные ребра и петли. Простой граф

Если в множестве 𝐸 есть несколько ребер, заданных одной и той же парой (𝑣,𝑢) называется кратным ребром.

Количество вхождений ребра – его кратность.

Если в множество 𝐸 входит ребро, заданное парой(𝑣,𝑣), то такое ребро пара называется петлей.

Псевдограф – допускаются петли и кратные ребра.
Мультиграф – допускаются только кратные ребра.
Простой граф – в графе нет ни петель, ни кратных ребер.

Понятия смежности и инцидентности

Если 𝑒=(𝑢,𝑣) – ребро графа 𝐺, то вершины 𝑢 и 𝑣 называются смежными (соседними) или концами ребра 𝑒.

В случае ориентированного графа для дуги 𝑒⃗= (𝑢,𝑣⃗⃗) вершина 𝑢–начальная, вершина 𝑣–конечная.

Также говорят, что дуга 𝑒⃗ исходит из вершины 𝑢 и заходит в вершину 𝑣.

Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро 𝑒 (дуга 𝑒⃗) инцидентно вершинам 𝑢 и 𝑣,
а также, что вершины 𝑢 и 𝑣 инцидентны ребру 𝑒 (дуге 𝑒⃗).

Степень вершины. Теорема о сумме степеней вершин графа, лемма о рукопожатиях.

Степень вершины (локальная степень вершины) – количество ребер, инцидентных ей. Договоримся петлю учитывать дважды.

Вершина, не инцидентная никакому ребру, называется изолированной.

Граф называется конечным, если число его ребер конечно.

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

Теорема. В конечном графе сумма степеней вершин равна удвоенному количеству ребер.

Теорема остается справедливой и при наличии петель, если только в степенях вершин считать их дважды.

Следствие 1. В конечном графе количество ребер равно полусумме степеней вершин.
Следствие 2 (лемма о рукопожатиях). В конечном графе число вершин нечетной степени четно.
(Количество человек, совершивших нечетное число рукопожатий, четно.)

Полный граф. Количество ребер в полном графе

Полный граф – простой неориентированный граф с 𝑛 вершинами и обозначается 𝐾𝑛, если в нем любые две различные вершины смежны.

Количество ребер в 𝐾𝑛. Степень каждой вершины графа 𝐾𝑛 равна (𝑛−1), а количество ребер равно полусумме степеней вершин, то есть 𝑛(𝑛−1) / 2=𝐶2𝑛.

Способы задания графов

В теории графов классическим способом представления графа служит матрица инциденций (инцидентностей).

Связность графов

Подграф

Граф 𝐻=(𝑈,𝐹) называется подграфом графа 𝐺=(𝑉,𝐸), если 𝑈⊆𝑉,𝐹⊆𝐸.

Пути и циклы можно рассматривать как подграфы графа 𝐺.

Пути и циклы в графе. Связность неориентированных графов

Цепь – путь без повторения ребер.

Простой путь – цепь, в которой не повторяются вершины. Нетрудно видеть, что из любой цепи можно выделить простой путь.

Путь называется замкнутым, если 𝑣𝑖0=𝑣𝑖𝑘.

Замкнутый путь называется циклом, если ребра в нем не повторяются.

Цикл называется простым, если вершины, кроме первой и последней, в нем не повторяются.

Длина[𝑢,𝑣]-пути – количество ребер в нем.

По определению граф 𝐺=(𝑉,𝐸), где |𝑉|=1, 𝐸=∅, является связным.

Из определений следует, что

полный граф является связным;
связный граф не обязательно полный.

Компонента связности неориентированного графа

Подграф 𝐻=(𝑈,𝐹) неориентированного графа 𝐺=(𝑉;𝐸) называется компонентой связности графа 𝐺 если:

граф 𝐻 связный;
к графу 𝐻 нельзя добавить ни вершины, ни ребра из графа 𝐺, чтобы он остался связным.

Очевидно, что связный граф состоит из одной компоненты.

Деревья

Определение дерева, свойства дерева

Дерево – связный граф без циклов (связный ациклический граф).

Свойство 1. Пусть 𝑇=(𝑉,𝐸)–дерево, 𝑢,𝑣∈𝑉,(𝑢,𝑣)∉𝐸. Если добавить ребро (𝑢,𝑣), то в графе появится цикл.
Свойство 2. Пусть 𝑇=(𝑉,𝐸)–дерево, 𝑢,𝑣∈𝑉,(𝑢,𝑣)∈𝐸. Если удалить ребро (𝑢,𝑣), то граф перестанет быть связным.
Свойство 3. Пусть 𝑇=(𝑉,𝐸)–дерево. Если |𝑉|=𝑛, то |𝐸|=𝑛−1.

Доказательство.

Доказательство легко проводится индукцией по числу вершин.

Для 𝑛 = 1утверждение, очевидно, справедливо.
Пусть 𝑛 > 1. Тогда в дереве существует концевая вершина 𝑢.
Удаляя из дерева vи ребро (𝑢,𝑣), инцидентное 𝑢,
получим дерево с 𝑛 − 1 вершиной, которое в силу индуктивного предположения имеет 𝑛 − 1 ребра.
Следовательно, первоначальное дерево имеет𝑛−2+1=𝑛−1 ребро.

Теорема. В дереве любые две вершины связаны единственным простым путем.

Остовное дерево

Пусть граф 𝐺=(𝑉,𝐸) связный, его подграф 𝐻=(𝑈,𝐹) называется остовным деревом, если

𝐻 – дерево;
𝑈=𝑉(множество вершин графа 𝐻 совпадает с множеством вершин графа 𝐺).

Если граф не является связным, то множество остовных деревьев его компонент связности называется остовным лесом.

Часть III Задачи на графах и алгоритмы их решения

Задача поиска в графах

Дано: Граф 𝐺 = (𝑉, 𝐸).
Надо: Найти вершину (вершины), обладающую заданным свойством P.

Алгоритм поиска в глубину

Алгоритм подобен щупальце, пытается дотянуться до самого дальнего элемента

Создаём стек вершин для просмотра
Создаём список просмотренных вершин
Выбираем начальную вершину
- Упорядочиваем узлы по номеру и берём первую
  
  либо
- Выбираем произвольную вершину
Добавляем начальную вершину в стек
Пока стек не пуст
- Берём элемент из стека
- Добавляем его в список просмотренных
- Ищем все такие узлы, которые соединены с текущим
- Если узел ещё не посещён и ещё не в стеке
  - Добавляем его в стек

Пример кода:

Graph.Nodes = Graph.Nodes.OrderBy(n => n.Id).ToList();

List<Node> visitedNodes = new List<Node>(); // посещённые узлы
Stack<Node> stack = new Stack<Node>(); // стек узлов к обработке
stack.Push(Graph.Nodes[0]); // добавляем первый узел

// пока очередь не пуста
while (stack.Count > 0)
{
    Node node = stack.Pop(); // достаём последний узел
    visitedNodes.Add(node); // считаем его обработанным

    // ищем все такие узлы, который соединены с текущим
    foreach (var n in Graph.Connections.Select(t => t.GetPairedNode(node)).Where(n => n != null).OrderBy(n => n.Id))
    {
        // если узел ещё не посещён и ещё не в стэке
        if (!visitedNodes.Contains(n) && !stack.Contains(n))
        {
            node.Children.Add(n); // добавляем дочерний узел
            n.Parent = node; // устанавливаем родительский узел
            stack.Push(n); // добавляем узел в стек обработки
        }
    }
}

Алгоритм поиска в ширину

Алгоритм подобен волне, просматривает ближайшие вершины, потом вершины на расстоянии 2 шагов, 3 и т.д.

Создаём очередь вершин для просмотра
Создаём список просмотренных вершин
Выбираем начальную вершину
- Упорядочиваем узлы по номеру и берём первую
  
  либо
- Выбираем произвольную вершину
Добавляем начальную вершину в очередь
Пока очередь не пуста
- Берём элемент из очереди
- Добавляем его в список просмотренных
- Ищем все такие узлы, который соединены с текущим
- Если узел ещё не посещён и ещё не в очереди
  - Добавляем его в очередь

Пример кода:

Graph.Nodes = Graph.Nodes.OrderBy(n => n.Id).ToList();

List<Node> visitedNodes = new List<Node>(); // посещённый узлы
Queue<Node> queue = new Queue<Node>(); // очередь узлов к обработке
queue.Enqueue(Graph.Nodes[0]); // добавляем первый узел
// пока очередь не пуста
while (queue.Count > 0)
{
    Node node = queue.Dequeue(); // достаём первый узел
    visitedNodes.Add(node); // считаем его обработанным
    // ищем все такие узлы, который соединены с текущим
    foreach (var n in Graph.Connections.Select(t => t.GetPairedNode(node)).Where(n => n != null).OrderBy(n=>n.Id))
    {
        // если узел ещё не посещён и ещё не в очереди
        if (!visitedNodes.Contains(n) && !queue.Contains(n))
        {
            node.Children.Add(n); // добавляем дочерний узел
            n.Parent = node; // устанавливаем родительский узел
            queue.Enqueue(n); // добавляем узел в очередь обработки
        }
    }
}

Задачи, которые можно решать с использованием модифицированных алгоритмов поиска

Задача о кратчайшем пути в заданный пункт назначения.
Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t).
Задача о кратчайшем пути между заданной парой вершин.
Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
Задача о кратчайшем пути между всеми парами вершин.
Требуется найти кратчайший путь из каждой вершины u в каждую вершину v.

Взвешенные графы

Определение взвешенного графа. Вес графа. Матрица весов.

Пусть 𝐺 = (𝑉, 𝐸) – граф (ориентированный или неориентированный)
Пусть каждому ребру 𝑒 сопоставлено некое действительное число 𝑐(𝑒). Тогда 𝑐 называется весовой функцией, а 𝑐(𝑒) – весом ребра 𝑒 (длиной, стоимостью).
Граф G с весовой функцией 𝑐 называется взвешенным графом и обозначается 𝐺 = (𝑉, 𝐸, 𝑐).

Весом графа 𝐻 называется число 𝑐(𝐻), равное сумме весов ребер графа 𝐻.

Матрица весов представляет из себя матрицу смежностей, где вместо 0 и 1 указаны веса рёбер соединяющих вершины.

Алгоритм Краскала

Остовное дерево с минимальным весом можно найти, применяя «жадный алгоритм»,
На каждом шаге выбирается новое ребро с наименьшим весом, не образующее цикл с уже выбранными ребрами.

Процесс останавливается, когда выбрано 𝑛 − 1 ребро.

Очевидно, что выбранные на каждом шаге алгоритма ребра образуют лес – граф, компоненты которого – деревья.

Пример кода:

Graph graph = new Graph(); // создаём временный граф
graph.Nodes.AddRange(Graph.Nodes); // копируем в него все узлы

float sum = 0f;

// сортируем рёбра по весам
var connections = Graph.Connections.OrderBy(c => c.ToString()).GroupBy(c => c.Length).SelectMany(g => g).ToList();

// обрабатываем рёбра
for (var i = 0; i < connections.Count - 1; i++)
{
    // добавляем ребро в граф
    graph.Connections.Add(connections[i]); 

    // если в графе появился цикл
    if (graph.HasLoop())
    {
        // удяляем это ребро
        graph.Connections.Remove(connections[i]);
    }
    else
    {
        sum += connections[i].Length;
    }
}

Алгоритм Прима

Этот алгоритм еще называют «алгоритм ближайшего соседа», он является модификацией «жадного» алгоритма с условием,
что на каждом шаге алгоритма выбранные ребра являются ребрами связного графа без циклов (дерева).

Кроме списка ребер остовного дерева будем поддерживать список вершин 𝑈, еще не включенных в дерево.
Для каждой вершины 𝑣 ∈ 𝑈 графа поддерживается минимальное расстояние до множества 𝑉 ∖ 𝑈 ранее включенных в него вершин.

Простыми словами:

Выбираем начальную вершину
Ищем все вершины, которые на текущий момент соединены с деревом и добавляем ближайшее.
Повторяем, пока все вершины не окажутся подключенными к дереву

Пример кода:

float sum = 0f;

// текущее дерево графа
List<Node> tree = new List<Node>();

// выбираем случайный узел
Node node = Graph.Nodes[0];
tree.Add(node); // добавляем его в дерево

// пока дерево меньше чем граф
while (tree.Count < Graph.Nodes.Count)
{
    // выбираем такие рёбра, которые соединены с деревом, но не ещё не подключены к нему
    var connections =
        Graph.Connections
            .Where(c =>
                tree.Contains(c.Node1) && !tree.Contains(c.Node2) ||
                !tree.Contains(c.Node1) && tree.Contains(c.Node2)
            ).OrderBy(c => c.ToString()).ToList();

    // сортируем рёбра по весу и выбираем первое
    var connection = connections.OrderBy(c => c.Length).First();

    sum += connection.Length;

    // если дерево содержит 1 узел ребра, добавляем второе и наоборот
    if (tree.Contains(connection.Node1))
    {
        tree.Add(connection.Node2);
    }
    else
    {
        tree.Add(connection.Node1);
    }
}

Задача о кратчайшем пути в сети

Задача о кратчайшем пути — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.

Постановка задачи, особенности графов, для которых такую задачу можно формулировать

Постановка задачи:

Дано: Сеть 𝐺 = (𝑉, 𝐸, 𝑐) и две выделенные вершины 𝑠 и 𝑡, |𝑉| = 𝑛, |𝐸| = 𝑚.
Надо: Найти кратчайший [𝑠, 𝑡]-путь.
- Более общая задача – найти путь между выделенной вершиной и всеми остальными вершинами

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

Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.

Алгоритм Форда-Беллмана. Дерево кратчайших путей.

Основная идея алгоритма Форда-Беллмана заключается в поэтапном вычислении кратчайших расстояний.

Предположим, есть ориентированный взвешенный граф G, который имеет n вершин и m рёбер, и определена некая вершина v.

Необходимо определить длины самых коротких путей от вершины v до каждой другой вершины.

Зададим массив расстояний d[0 … n – 1], который по завершению выполнения алгоритма содержит итоговый результат.

d[v] = 0, а другие элементы d[] = inf

Алгоритм состоит из нескольких фаз.

Во всех фазах выполняется просмотр всех рёбер графа, и согласно алгоритму делается попытка релаксации (rеlax, ослабления) по направлению каждого ребра (а, b) стоимости с.

Релаксацией ребра (a, b) называется уменьшение значения d[b] до d[a] + c (если второе значение меньше первого).

Граф, образованный множеством 𝐸 (пары соединённых вершин) и множеством выделенных дуг, можно назвать деревом кратчайших путей из вершины 1 во все остальные вершины.

Эйлеровы пути и циклы

Определение эйлерова пути, эйлерова цикла, эйлерова графа

Эйлеров путь в графе – путь, проходящий через каждое ребро графа в точности один раз

Эйлеров цикл в графе – замкнутый эйлеров путь

Эйлеров граф – граф, в котором есть эйлеров цикл

Критерий существования эйлерова цикла (пути) в графе)

Теорема Эйлера 1

Эйлеров путь в графе существует тогда и только тогда, когда граф

Связный
Содержит не более чем две вершины нечетной степени (0 или 2)

Теорема Эйлера 2

Конечный граф 𝐺 = (𝑉, 𝐸) содержит эйлеров цикл тогда и только тогда, когда одновременно выполнены следующие условия:

𝐺 связен;
Степени всех его вершин четные.

Теорема Эйлера 3

Граф 𝐺 = (𝑉, 𝐸) содержит эйлеров цикл, тогда и только тогда, когда

Множество его ребер можно разбить на простые непересекающиеся циклы.

Алгоритм построения эйлерова цикла в эйлеровом графе

Пользуясь последней теоремой Эйлера

Выбираем любую вершину графа
Пока есть цикл, проходящий через текущую вершину
- Цикл ищем поиском в глубину
  - Добавляем все рёбра цикла в ответ
  - Удаляем все вершины из графа
Для каждой вершины учтённых на прошлом шаге циклах
- Рекурсивно повторяем шаги 2,3

Гамильтоновы пути и циклы

Определение гамильтонова пути, гамильтонова цикла

Гамильтонов путь в графе – путь, проходящий через каждую вершину графа в точности один раз

Гамильтонов цикл в графе – замкнутый гамильтонов путь

Гамильтонов граф – граф, в котором есть гамильтонов цикл

Оценка количества гамильтоновых циклов п полном графе

Не известен алгоритм, который проверял бы существование гамильтонова пути в произвольном графе, используя f(n) шагов.

Худший случай – нет гамильтоновых путей

В худшем случае в полном графе требуется рассмотреть все перестановки O(n!)
В худшем случае в неориентированном графе нужно просмотреть (n-1)!/2 перестановок.

Достаточные условия существования гамильтонова цикла (n – число вершин графа, u,v – 2 вершины, deg(u) – степень вершины)

Теорема Оре
- Если 𝑛 >= 3 и deg(𝑢) + deg(𝑣) >= 𝑛 для любых несмежных 𝑢, 𝑣, то в заданном графе есть гамильтонов цикл.
Условие Дирака
- Если 𝑛 >= 3 и deg(𝑣) >= 𝑛 / 2 для сех 𝑣, то в заданном графе есть гамильтонов цикл

Переборный алгоритм нахождения гамильтонова пути в графе, либо доказательства отсутствия ГЦ

На основе условий:

В полном графе каждому гамильтонову циклу соответствует перестановка множества вершин (не одна!).
И наоборот – каждой перестановке соответствует гамильтонов цикл.

Просматриваем (перебираем) все перестановки множества вершин графа.

Для каждой перестановки проверяем: соответствует ли ей цикл в графе.

Задача коммивояжера

Постановка задачи

Дано: Полный взвешенный граф 𝐺 = (𝑉, 𝐸, 𝑐), |𝑉| = 𝑛.

Надо: Найти гамильтонов цикл с наименьшим весом.

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

Эвристические алгоритмы решения задачи коммивояжера

«Жадная» эвристика.
Начинаем из вершины с наименьшим номером,
выбираем ребро с минимальным весом,
включаем его в путь.

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

(Примерно как в алгоритме Прима)
Использование остовного дерева с минимальным весом.

Построенный цикл будет не более, чем в два раза «тяжелее» оптимального.
- 1 шаг: строим остовное дерево с минимальным весом.
- 2 шаг: удваиваем ребра построенного дерева.
- 3 шаг: в полученном графе строим эйлеров цикл.
- 4 шаг: из полученного цикла удаляем повторяющиеся вершины.
- В результате получится гамильтонов цикл.

Связность ориентированных графов: слабая связность, односторонняя достижимость, сильная связность

Связный граф — граф, в котором есть хотя бы одна пара соединённых вершин.

Сильносвязный граф – граф, в котором для любой пары вершин найдётся прямая связь (ребро). (Аналог полного графа)

Слабосвязный граф – граф, в котором для любой пары вершин найдётся хотя бы 1 маршрут соединяющий их.

Односторонне достижимый граф – граф, в котором для хотя бы 1 пары вершин найдётся путь A-B, но не B-A

Несвязный граф – граф, в котором найдётся хотя бы 1 пара вершин, для которой нельзя построить маршрут, соединяющий их.

Компонента связности – Максимальный связный подграф неориентированного графа

Существуют два вида связности:

Число вершинной связности – это наименьшее число вершин, удаление которых (вместе с инцидентными ребрами) приводит к несвязному графу.
Число реберной связности– это наименьшее число ребер, удаление которых приводит к несвязному графу.

Источник

Как посчитать ребра графа

Полный граф
K₇ , полный граф с 7 вершинами
Вершин	n
Рёбер	n ( n − 1 ) 2 <displaystyle <frac <2>>>
Диаметр	1
Автоморфизмы	n! (S_n)
Хроматическое число	n
Хроматический индекс	n если n — нечётное, иначе n − 1
Обозначение	K_n
Медиафайлы на Викискладе

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с n <displaystyle n> вершинами имеет n ( n − 1 ) / 2 <displaystyle n(n-1)/2> рёбер и обозначается K n <displaystyle K_> . Является регулярным графом степени n − 1 <displaystyle n-1> .

Полный граф образуется из вершин и ребер (n-1)-симплекса.

По́лный ориенти́рованный граф — ориентированный граф, в котором каждая пара различных вершин соединена парой дуг (с различными направлениями).

Графы с K 1 <displaystyle K_<1>> по K 4 <displaystyle K_<4>> являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф K 5 <displaystyle K_<5>> и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.

Примеры [ править | править код ]

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.

Введение

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

Понятие графа

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.

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

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Графы Эйлера

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3×3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Решение. Занумеруем клетки доски, как показано на рисунке:

Каждой клетке поставим в соответствие точку на плоскости и, если из одной клетки можно попасть в другую ходом шахматного коня, то соответствующие точки соединим линией. Исходная и требуемая расстановки коней показаны на рисунках:

При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. 9372 — | 7304 — или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Класс: 7

Презентация к уроку

Загрузить презентацию (486,9 кБ)

Внимание! Предварительный просмотр слайдов используется исключительно в ознакомительных целях и может не давать представления о всех возможностях презентации. Если вас заинтересовала данная работа, пожалуйста, загрузите полную версию.

Профиль класса: общеобразовательный.

Тип урока: изучение и первичное закрепление новых знаний.

Знания и умения учащихся:

ученик знает понятия графа и мультиграфа, знаком с понятиями “вершина графа” (смежные вершины) и “ребро графа” (кратные ребра и петли);
умеет приводить примеры использования графов в различных учебных предметах и повседневной жизни.

Образовательные:

закрепить понятие графа, сформировать представление о степени вершины графа (четная, нечетная вершины), сформулировать определение о связности графа, рассмотреть утверждение о количестве ребер графа и теорему о четности числа нечетных вершин графа;
отработать навыки использования теоретических знаний для решения новых задач.

Развивающие:

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

Воспитательная:

воспитывать культуру общения на уроке, взаимоуважение.

План урока

Организационный момент (приветствие класса, подготовка к уроку, проверка домашнего задания, включающая повторение материала предыдущего урока);
Теоретический материал (знакомство с темой предстоящего урока, объяснение нового материала и краткая запись в рабочую тетрадь новых теоретических сведений по теме урока);
Закрепление материала (решение задач);
Итоги урока (краткий вывод и домашнее задание).

Давайте вспомним основные понятия теории графов. Для этого проведем разминку по типу незаконченного предложения (Презентация, сл.: 2, 3, 4). Каждый ученик имеет карточки с пропущенными словами в предложение. Учитель зачитывает предложение, останавливаясь перед пропущенным словом, и выбирает ученика, который в свою очередь должен поднять карточку. Далее этот ученик читает дальше предложение, также останавливаясь перед пропущенным словом, и уже сам выбирает одноклассника для ответа и т. д. по цепочке.

Проверим в классе решение домашней задачи (Презентация, сл.: 5, 6, 7). Один ученик выходит к доске и рисует граф. Далее мы вместе проверяем ребра (дороги между городами), считаем количество выходящих ребер из каждой вершины и смотрим связи между городами.

Сегодня на уроке мы продолжим изучение графов, познакомимся с понятием “степень вершины графа” и сформулируем определение связности графа (обратим внимание на наш граф из домашнего задания и определим, является ли он связным или нет и почему). Рассмотрим утверждение о количестве ребер графа, и проверим в соответствие с этим утверждением, правильно ли мы посчитали количество ребер графа в домашней задаче. И рассмотрим теорему о четности числа нечетных вершин графа.

Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли будем считать, что это ребро выходит из вершины дважды (Презентация, сл. 8).

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

Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной (Презентация, сл. 9).

Запишем определение в тетрадь и перечислим через запятую сначала четные вершины, а потом нечетные вершины для уже нарисованного графа. Проверим задание вслух.

Количество ребер графа равно половине суммы степеней его вершин. Пусть граф имеет n вершин, тогда число ребер равно:

(Презентация, сл. 10)

Запишем утверждение в рабочую тетрадь и посчитаем количество ребер графа в домашней задачке. Проверим ответ в классе. Рассмотрим задачу и ее решение на подсчет числа ребер графа без построения. (Презентация, сл. 11).

Сформулируем теорему о количестве вершин нечетной степени любого графа и запишем формулировку в рабочую тетрадь. (Презентация, сл. 12).

Теорема. Количество вершин нечетной степени любого графа всегда четно.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин.

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

А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Разберем доказательство и проверим теорему на нашей домашней задачке.

Рассмотрим несколько задач.

Задача. В государстве 50 городов, из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих дорог из городов: 50 * 4 = 200. Однако, мы понимаем, что при подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 100.

Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?

Ответ. Нет (теорема о четности числа нечетных вершин).

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

В качестве домашнего задания ученики получать карточки с тремя задачами (Презентация, сл. 13).

Источник

Комбинаторные свойства[править | править код]

Геометрические и топологические свойства[править | править код]

Число пересечений[править | править код]

Число прямолинейных пересечений[править | править код]

Планарность и книжная толщина[править | править код]

Симплексы и многогранники[править | править код]

Зацепленность и заузленность[править | править код]

Примеры[править | править код]

Примечания[править | править код]

Литература[править | править код]

Оглавление

Введение. Теория множеств

Часть I Комбинаторика

1. Основные правила комбинаторики

2. Перестановка. Факториал

3. Классические задачи комбинаторики

4. Выборки

5. Бином Ньютона. Биномиальные коэффициенты. Полиномиальные коэффициенты.

6. Вычисление сумм точное и приближенное

7. Оценка сложности фрагментов программы

Часть II Теория графов

1. Основные определения

2. Способы задания графов

3. Связность графов

4. Деревья

Часть III Задачи на графах и алгоритмы их решения

Задача поиска в графах

Взвешенные графы

Задача о кратчайшем пути в сети

Эйлеровы пути и циклы

Гамильтоновы пути и циклы

Задача коммивояжера

Связность ориентированных графов: слабая связность, односторонняя достижимость, сильная связность

Теория множеств

Понятие множества

Способы задания множества

Операции над множествами

Комбинаторика

Основные правила комбинаторики

Правило суммы

Правило произведения

Перестановка. Факториал

Классические задачи комбинаторики

Выборки

Бином Ньютона. Биноминальные и полиномиальные коэффициенты

Вычисление сумм: точное и приближённое

Оценка сложности фрагмента программы

Теория графов

Основные определения

Определение графа

Ориентированные и неориентированные графы

Геометрическая интерпретация графа

Кратные ребра и петли. Простой граф

Понятия смежности и инцидентности

Степень вершины. Теорема о сумме степеней вершин графа, лемма о рукопожатиях.

Полный граф. Количество ребер в полном графе

Способы задания графов

Связность графов

Подграф

Пути и циклы в графе. Связность неориентированных графов

Компонента связности неориентированного графа

Деревья

Определение дерева, свойства дерева

Остовное дерево

Часть III Задачи на графах и алгоритмы их решения

Задача поиска в графах

Алгоритм поиска в глубину

Алгоритм поиска в ширину

Задачи, которые можно решать с использованием модифицированных алгоритмов поиска

Взвешенные графы

Определение взвешенного графа. Вес графа. Матрица весов.

Алгоритм Краскала

Алгоритм Прима

Задача о кратчайшем пути в сети

Постановка задачи, особенности графов, для которых такую задачу можно формулировать

Алгоритм Форда-Беллмана. Дерево кратчайших путей.

Эйлеровы пути и циклы

Определение эйлерова пути, эйлерова цикла, эйлерова графа

Критерий существования эйлерова цикла (пути) в графе)

Теорема Эйлера 1