Дискретная математика, Графы, матроиды, алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010


Дискретная математика, Графы, матроиды, алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010.

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

Дискретная математика, Графы, матроиды, алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010


БЛОКИ И ТОЧКИ СОЧЛЕНЕНИЯ.
Пусть G = (V, Е) — произвольный граф. Вершина v называется точкой сочленения, если граф G — v имеет больше компонент связности, чем граф G.

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

Блоком графа G называется любой его максимальный неразделимый подграф. На рис. 10,а показаны точки сочленения и, v некоторого связного графа, а на рис. 10,6 приведены его блоки.

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



Бесплатно скачать электронную книгу в удобном формате и читать:

Скачать книгу Дискретная математика, Графы, матроиды, алгоритмы, Асанов М.О., Баранский В.А., Расин В.В., 2010 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать




Скачать - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: :: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 


Книги, учебники, обучение по разделам




Не нашёл? Найди:





2017-09-20 22:58:30