Details

Title: Алгоритмический подход к исследованию минимальных и минимальных по стягиванию k-связных графов: выпускная квалификационная работа бакалавра: направление 01.03.02 «Прикладная математика и информатика» ; образовательная программа 01.03.02_02 «Системное программирование»
Creators: Зубкова Дарья Андреевна
Scientific adviser: Пастор Алексей Владимирович
Other creators: Арефьева Людмила Анатольевна; Чуканов Вячеслав Сергеевич
Organization: Санкт-Петербургский политехнический университет Петра Великого. Институт прикладной математики и механики
Imprint: Санкт-Петербург, 2021
Collection: Выпускные квалификационные работы; Общая коллекция
Subjects: k-связность; минимальность; минимальность по стягиванию; графы; k-connection; minimum; contraction minimum; graphs
Document type: Bachelor graduation qualification work
File type: PDF
Language: Russian
Level of education: Bachelor
Speciality code (FGOS): 01.03.02
Speciality group (FGOS): 010000 - Математика и механика
Links: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2021/vr/vr21-1823
Rights: Доступ по паролю из сети Интернет (чтение, печать, копирование)
Record key: ru\spstu\vkr\13783

Allowed Actions:

Action 'Read' will be available if you login or access site from another network Action 'Download' will be available if you login or access site from another network

Group: Anonymous

Network: Internet

Annotation

Работа посвящена разработке алгоритма проверки графов на свойства минимальности, минимальности по стягиванию и k-связности. Цель работы — поиск минимальных и минимальных по стягиванию k-связных графов. Настоящая выпускная квалификационная работа содержит обзор существующих результатов исследований рассматриваемых графов, методов проверки на k-связность и вспомогательных методов. Исходя из рассмотренных данных, предложен алгоритм проверки входящих графов на свойства минимальности, минимальности по стягиванию и k-связности, а также поиск графов, обладающих такими свойствами внутри заданного на вход графа. Результатом работы является программа, реализующая алгоритм проверки графов на свойства k-связности, минимальности и минимальности по стягиванию, алгоритм поиска графов, обладающих предыдущими свойствами.

The work is devoted to the development of an algorithm for checking graphs for the properties of minimality, minimality in contraction and k-connectivity. The work is devoted to the development of an algorithm for checking graphs for the properties of minimality, minimality in contraction and k-connectivity. The purpose of this work is to find minimal and minimal contraction k-connected graphs. This final qualifying work contains an overview of existing research results of the considered graphs, k-connectivity verification methods and auxiliary methods. Based on considered data, an algorithm is proposed for checking incoming graphs for properties of minimality, contraction minimality and k-connectivity, as well as for searching for graphs with such properties inside the graph given at the input. The result of the work is a program that implements an algorithm for checking graphs for the properties of k-connectivity, minimality and contraction minimality, an algorithm for finding graphs with the previous properties.

Document access rights

Network User group Action
ILC SPbPU Local Network All Read Print Download
External organizations N2 All Read
External organizations N1 All
Internet Authorized users SPbPU Read Print Download
Internet Authorized users (not from SPbPU, N2) Read
Internet Authorized users (not from SPbPU, N1)
-> Internet Anonymous

Usage statistics

stat Access count: 10
Last 30 days: 1
Detailed usage statistics