Дискретная математика, Графы, матроиды, алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010.
В учебном пособии изложен ряд основных разделов теории графов и матроидов. Рассмотрены алгоритмы дискретной оптимизации на сетях и графах, наиболее часто используемые программистами.
Пособие предназначено для студентов и аспирантов, специализирующихся в области компьютерных наук и информационной безопасности, для практикующих программистов, для всех желающих изучить основы современной дискретной компьютерной математики.
БЛОКИ И ТОЧКИ СОЧЛЕНЕНИЯ.
Пусть G = (V, Е) — произвольный граф. Вершина v называется точкой сочленения, если граф G — v имеет больше компонент связности, чем граф G.
Связный граф называется неразделимым, если он не содержит точек сочленения.
В связном графе полезно выделить максимальные неразделимые подграфы. Это можно сделать подобно тому, как в произвольном графе были выделены максимальные связные подграфы (компоненты связности).
Блоком графа G называется любой его максимальный неразделимый подграф. На рис. 10,а показаны точки сочленения и, v некоторого связного графа, а на рис. 10,6 приведены его блоки.
Очевидно, любой неразделимый подграф графа содержится в некотором его блоке. Поэтому любое ребро лежит в некотором блоке; то же самое относится и к произвольному циклу. Ясно, что любой блок связного неодноэлементного графа сам неодноэлементен.
Купить .
Теги: учебник по математике :: математика :: Асанов :: Баранский :: Расин
Смотрите также учебники, книги и учебные материалы:
- Математическая логика, Ершов Ю.Л., Палютин Е.А., 1987
- Занимательная математика, Множества и отношения, Дунаев В.В., 2008
- Математика, алгебра и начала математического анализа, 11 класс, Виленкин Н.Я., Ивашев-Мусатов О.С., Шварцбурд С.И., 2014
- Математика, алгебра и начала математического анализа, 10 класс, Виленкин Н.Я., Ивашев-Мусатов О.С., Шварцбурд С.И., 2014
- Основы дискретной математики, учебное пособие для студентов вузов, Гаджиев А.А., 2005
- Занимательная логика, Кольман Э., Зих О., 1966
- Введение в математическую логику, Колмогоров А.Н., Драгалин А.Г., 1982
- Математика для мам и пап, Домашка без мучений, Роб Истуэй, Майк Эскью, 2017