Дискретная математика. Ч. 2 (190,00 руб.)

М. А. Башкин, О. П. Якимова ДИСКРЕТНАЯ МАТЕМАТИКА Часть 2 Сборник задач Рекомендовано Научно-методическим советом университета для студентов, обучающихся по направлению Математика и компьютерные науки, специальности Компьютерная безопасность Ярославль ЯрГУ 2013 1 УДК 519.854(076.1) ББК В174я73-4 Б 33 Рекомендовано Редакционно-издательским советом университета в качестве учебного издания. <...> План 2013 года Рецензент кафедра компьютерной безопасности и математических методов обработки информации ЯрГУ Б 33 Башкин, М. А. Дискретная математика. <...> Рисуя граф, обычно изображают каждую вершину точкой и соединяют линиями такие пары точек, которым в графе соответствует пара вершин, образующая ребро. <...> Число вершин графа G будем обозначать через n(G), число ребер – через m(G). <...> Подграф G0 на подмножестве вершин V0 ⊆ V называется порожденным, если множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат V0. <...> Ориентированный граф состоит из конечного непустого множества V вершин и заданного набора X2 упорядоченных пар различных вершин. <...> Мультиграфом называется граф, в котором пары вершин могут соединяться более чем одним ребром; эти ребра называются кратными. <...> Дальнейшее обобщение состоит в том, что, кроме кратных ребер, допускаются еще и петли, то есть ребра, соединяющие вершину саму с собой. <...> Степенью вершины графа G называется число инцидентных ей ребер. <...> Традиционно принято обозначать через dv степень вершины v, через ∆ (G) – наибольшую из степеней вершин графа. <...> Вершина степени 0 называется изолированной, вершина степени 1 – концевой (висячей). <...> Сумма степеней всех вершин графа равнa удвоенному числу ребер Пример 1. <...> Полный граф на n вершинах обозначается Kn. <...> Полный двудольный граф, доли которого состоят из p и из q вершин, обозначается символом Kp,q. <...> Максимальные по включению подграфы графа G, порожденные классами эквивалентных вершин, называются компонентами связности графа G. <...> Какое максимальное количество <...>