Вариант 1. Автоматизированное проектирование телекоммуникационных сетей

  • ID: 29964 
  • 5 страниц

Фрагмент работы:

Сибирский государственный университет телекоммуникаций и информатики

Дистанционное обучение

«Автоматизированное проектирование телекоммуникационных сетей». Экзамен

Билет № 1

Основные понятия теории графов.

Паросочетания и реберные покрытия.

1. Основные понятия теории графов.

называется пара , где - непустое множество элементов, называемых графа, а - множество неупорядоченных пар элементов из , называемых графа.

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