#Проектное решение

====
#смежными;
====
конечными вершинами этого ребра;
====
инцидентными друг другу;
====
несмежными.

++++

Как называют граф, у которого множества вершин и ребер пустые:
====
#устым;
====
непустым;
====
нуль-графом;
====
невидимым.

++++

Как называют ребра, инцидентные одной и той же паре вершин:
====
#смежными;
====
кратными;
====
петлей;
====
инцидентными друг другу.

++++

Как называют ребро, соединяющее любую вершину саму с собой:
====
инцидентным само по себе;
====
гамильтоновым;
====
#петлей;
====
смежным другом ребру.

++++

Граф с петлями и кратными ребрами называют:
====
#псевдографом;
====
мультиграфом;
====
нуль-графом;
====
обычным.

++++

Как называют конечный неориентированный граф без петель и кратных ребер:
====
псевдографом;
====
обычным;
====
нуль-графом;
===
#мультиграфом.

++++

Если пары (v_i, v_j) считают упорядоченными, то граф называют:
====
псевдографом;
====
мультиграфом;
====
нуль-графом;
====
#орграфом.

++++

Ребра ориентированного графа называют:
====
#дугами;
====
петлями.

++++

Граф, имеющий как ребра, так и дуги, называют:
====
орграфом;
====
мультиграфом;
====
обычным;
====
#смешанным.

++++

Если множества вершин и ребер графа конечные, то граф является:
====
бесконечным;
====
взвешенным;
====
смешанным;
====
#конечным.

++++

Порядком графа называют:
====
#количество вершин;
====
количество ребер;
====
множество ребер;
====
множество вершин.

++++

Локальная степень вершины v графа G – это:
====
количество вершин в графе G;
====
#количество ребер, инцидентных вершине v;
====
вес ребер, инцидентных вершине v;
====
кратность ребер, инцидентных вершине v.

++++

Конечный неориентированный граф без петель и ребер – это:
====
#простой граф;
====
суграф;
====
взвешенный граф;
====
нуль-граф.

++++

Количество ребер маршрута называют его:
====
порядком;
====
плотностью;
====
#длиной;
====
размерностью.

++++

Маршрут М называют цепью, если каждое ребро встречается в нем:
====
не менее одного раза;
====
#не более одного раза;
====
не более двух раз;
====
не менее двух раз.

++++

Если первая вершина маршрута совпадает с последней, то маршрут называют:
====
незамкнутым;
====
простым;
====
сложным
====
#замкнутым.

++++

Если цепь является замкнутой, то ее называют:
====
простым деревом;
====
простым циклом;
====
деревом;
====
#циклом.

++++

Если каждая вершина встречается в маршруте не более чем один раз, то его называют:
====
простым циклом;
====
#цепью;
====
циклом;
====
простой цепью.

++++

Маршрут в ориентированном графе называют:
====
циклом;
====
обходом;
====
#путем;
====
цепью.

++++

В обычном графе маршрут можно задавать последовательностью его:
====
#вершин;
====
петель;
====
цепей;
====
циклов.

++++

Кто является основателем теории графов?

====
Гамильтон;
====
#Эйлер;
====
Кантор;
====
этот человек не известен науке.

++++

Какую задачу решал Эйлер:
====
графопостроения;
====
пути от пункта А до пункта Б,
====
#о Кенигсбергских мостах;
====
кратчайшего пути.

++++

Сколько раз одно и то же ребро может встречаться в маршруте:
====
ни разу;
====
#один раз;
====
два раза;
====
сколько угодно.

++++
Одним из главных результатов теории алгоритмов является доказательство существования

====
#некоторых неразрешимых проблем
====
решения любой задачи
====
некоторых решаемых проблем
====
 алгоритма Маркова решения любой задачи


++++


Основным свойством конструктивного подхода к понятию алгоритма является то, что все множество функций строится
====
#из конечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых очевидна
====
из бесконечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых очевидна
====
из конечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых не очевидна
====
из бесконечного числа исходных объектов - базиса с помощью простых операций, эффективная выполнимость которых не очевидна


++++


Полиномиальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид