Основы теории графов
З
адан
граф G(V,E):
Несмежными рёбрами являются…
а) е1,е2; е2,е3; е3,е4; е4,е1;
б) е1,е5; е2,е5; е3,е5; е4,е5;
в) е1,е3; е2,е4.
Задан граф G(V,E):
Смежными рёбрами являются…
а) е1, е2; е2,е3; е3,е4; е4,е1;
б) е1,е5; е2,е5; е3,е5; е4,е5;
в) е1,е3; е2,е4.
Количество рёбер инцидентных вершине v называют степенью d(v) или валентностью, где p – число вершин…
а) d(v) ≥ 0;
б) d(v) ≤ р-1;
в) d(v) ≤ р(р-1)
Если степень вершины равна нулю, d(v)=0, то вершину называют…
а) концевой;
б) начальной;
в) изолированной.
Если степень вершины равна 1, то вершину называют…
а) концевой;
б) начальной;
в) изолированной.
Задан граф G(V,E):
В графе G(V,E) маршрут (v1-v3-v1,v4) – это…
а) маршрут, но не цепь;
б) цепь, но не простая;
в) простая цепь.
Задан граф G(V,E):
В графе G(V,E) маршрут (v1-v3-v5-v2-v3-v4) – это…
а) маршрут, но не цепь;
б) цепь, но не простая;
в) простая цепь.
Задан граф G(V,E):
В графе G(V,E) маршрут (v1-v4-v3-v2-v5) – это…
а) маршрут, но не цепь;
б) цепь, но не простая;
в) простая цепь.
Задан граф G(V,E):
В графе G(V,E) маршрут (v1-v3-v5-v2-v3-v4-v1) – это…
а) простая цепь;
б) цикл, но не простой цикл;
в) простой цикл.
Задан граф G(V,E):
В графе G(V,E) маршрут (v1-v3-v4) – это…
а) простая цепь;
б) цикл, но не простой;
в) простой цикл.
Длина кратчайшей цепи между вершинами u, v (<u,v>) называется…
а) диаметр;
б) ярус;
в) расстояние.
В графе G(V,E) наибольшая длина из кратчайших путей называется…
а) диаметр;
б) ярус;
в) расстояние.
Множество вершин, находящихся на одинаковом расстоянии от вершины называется…
а) диаметр;
б) ярус;
в) расстояние.
Полным графом с р вершинами, обозначенным Кр и имеющим максимально возможное число рёбер является…
а) q(Кр)=p-1/2;
б) q(Кр)=p(p-1);
в) q(Кр)=p(p-1)/2.
Если в орграфе полустепень захода вершины d+(v)=0, то вершина v …
а) источник;
б) сток;
в) сеть.
Если в орграфе полустепень исхода вершины d–(v)=0, то вершина v …
а) источник; б) сток; в) сеть.
Заданы диаграммы графов:
Изоморфными графами являются …
а) G1, G2, G3; b) G1,G2; c) G2, G3; d) G1, G3.
Количество рёбер d(), инцидентных вершине , называется …
a) степенью; b) маршрутом; c) инвариантом.
По теореме Эйлера сумма степеней вершин графа равна:
a) ∑d() = 2q; b) ∑d() = p(p-1); c) ∑d() = p(p-1) / 2;
Задан граф G(V1,E1).
Д
ополнением
G1(V1,E1)
является граф …
1
Заданы графы G1(V1,E1), G2(V2,E2):
Объединением графов является граф G (V,E): G1(V1,E1) U G2(V2,E2) …
4. нет правильного ответа
Дан граф G1(V1,E1) и граф G2(V2,E2):
Соединением графов G1 и G2 является граф G(V,E) = G1(V1,E1) + G2(V2,E2) …
3.
Дан граф G1(V1,E1):
Удаление вершины 2 приводит к графу G(V,E) …
2.
Дан граф G1(V1,E1):
Удаление ребра (2,4) приводит к графу G(V,E) …
1.
Дан граф G(V,E):
Добавление ребра е в граф G1(V1,E1) даёт граф G2(V2,E2), где V2:=V1&E2=E1U {e}…
4. нет правильного ответа.
Дан граф G(V,E):
Стягивание подграфа А графа G1(V1,E1) даёт граф G2(V2,E2), где V2:=(V1/А)U{} &
E2 := E1 /{e = (, ω)| є A V ω є A} U { e = (, )| є Г (А) / A} …
3.
Дан граф G(V,E):
Размножение вершины V графа G1(V1,E1) даёт граф G2(V2,E2), где
V2 := V1 U{'} & E2 := E1 U {(, ')} U { e = (, ')| є F+ ()}
