АвторыКнязьков В.С., Волченская Т.В.
Введение в теорию графов
ИздательствоИНТУИТ
Тип изданияучебник
Год издания2016
Скопировать биб. запись
Для каталогаКнязьков, В. С. Введение в теорию графов / Князьков В. С. , Волченская Т. В. - Москва : Национальный Открытый Университет "ИНТУИТ", 2016. - Текст : электронный // ЭБС "Консультант студента" : [сайт]. - URL : https://www.studentlibrary.ru/book/intuit_091.html (дата обращения: 21.11.2024). - Режим доступа : по подписке.
АннотацияПриводятся начальные сведения о графах, основные понятия и определения, способы представления графов. Рассматриваются основные операции над графами, такие как - объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. <br>Даются понятия прямых и обратных отображений для орграфов различных порядков, прямого и обратного транзитивного замыкания, приводятся способы нахождения транзитивных замыканий по матрице смежности и обсуждаются вопросы достижимости для орграфов, способы нахождения матриц достижимости и контрдостижимости. Рассматриваются типы графов и подграфов, такие как -полный, симметрический, антисимметрический, двудольный, древовидный, планарный и их возможные комбинации. Дается теорема о двудольности графов. Рассматривается матричный способ нахождения количества путей между любыми вершинами графа, методы разбиения графов на сильно связные подграфы- метод Мальгранжа и матричный метод. Даются понятия веса и длины пути, сведения о орциклах и циклах и их особенностях. Рассматриваются метод Дейкстра нахождения кратчайших путей и методика построения базы для взвешенного графа.