Решаването на изпитния тест е в рамките на 60 минути
На всеки въпрос е предложен само един правилен отговор
Оценяването се извършва по следния начин:
правилен отговор = 2 точки
грешен отговор = – 1 точка
без отговор = 0 точки
Оценка=2+, (k=сумата от точките)
Под граф се разбира: (а) геометрична структура в пространството, състояща се от точки, съединени със система от линейни сегменти; (б) схематично представяне на обекти и отношения между тях; (в) геометрична фигура, състояща се от точки (наречени върхове) и страни (наречени ребра).
Два графа G=(V,E) и G'=(V',E') са изоморфни един на друг, ако: (а) изображение на V във V', както и на Е в Е', запазващо инцидентността ; (б) взаимно-еднозначно изображение между V и V', между Е и Е', както и между и'; (в) биекция между V и V', както и между Е и Е', запазваща .
Ако е1(v&w) и е2(v&w), то ребрата е1 и е2 се наричат: (а) примки; (б) паралелни; (в) еднакви.
Прост граф G(n,m) съществува за: (а) m: 0m; (б) m: 0m; (в) m.
Един граф е правилен, ако: (а) върховете и ребрата му са равни на брой; (б) всеки връх е от една и съща степен; (в) степените на върховете са равни на степените на ребрата.
Структурата G1=(V1,E1,1) се нарича подграф на G=(V,E,), ако са изпълнени следните условия: (а) 1) V1V E1E; 2) 1(e)=(e) eE1; (б) 1) V1V E1E; 2) 1(e)=(e) eE1; 3) eE1, (e)=(v&w) vV1 wV1; (в) 1) V1V E1E; 2) 1(e)=(e) eE1; 3) eE1, (e)=(v&w) vV1 wV1.
Един маршрут е верига или цикъл, ако: (а) е затворен или незатворен; (б) е затворен или незатворен и освен това върховете му са различни; (в) ребрата му са различни.
Не е вярно, че: (а) свързан граф остава свързан след премахване на ребро това ребро принадлежи на някакъв цикъл; (б) свързан граф с k върха трябва да съдържа поне k –1 ребра; (в) свързан граф, който става несвързан при премахване на произволно ребро.
Скелет на G се нарича: (а) фактор на G, който е дърво; (б) подграф на G, който е дърво; (в) подграф на G с максимален брой ребра.
В краен правилен граф G от степен h: a) мост, ако h е нечетно число; (б) мост, ако h е четно число; (в) може да мост, ако h е четно число.
През два върха на графа елементарен цикъл след премахването на всички късове се получи: (а) нулев подграф; (б) ацикличен подграф; (в) подграф с повече от 1 ребро.
Разделящо множество от ребра на граф G: (а) винаги ; (б) , ако има поне 1 мост; (в) , ако G е пълен.
В свързан граф затворен маршрут и ребров разрез: (а) имат четен брой общи ребра; (б) нямат общи ребра; (в) имат нечетен брой общи ребра.
Граф G се нарича k-свързан (k2), когато или G е пълен граф от ред k+1 или: (а)има поне k+2 върха и множество с най-много k–1 върха, което да е върхов разрез; (б) множество от поне k–1 върха, което да не е върхов разрез; (в) има поне k+2 върха и множество с поне k–1 върха, което да е върхов разрез.
Не е вярно, че свързан граф G е 2-реброво свързан, ако: (а) е от ред поне 2-ри; (б) няма ребров разрез от 2 ребра; (в) не съдържа мост.
Граф G=(V,E) е k-делен, ако: (а), и във Vi (i=1,…k) няма съседни върхове; (б), и във Vi (i=1,…k) няма съседни върхове; (в) и във Vi (i=1,…k) няма съседни върхове.
Два ориентирани графа са изоморфни, ако: (а) съответните им неориентирани графи са изоморфни; (б) съответните им неориентирани графи са изоморфни и съответните дъги имат еднаква ориентация; (в) граничните върхове на две съответни дъги са наредени по един и същ начин.
Ормаршрут не е път, ако: (а) или е затворен или има повтарящи се върхове; (б) или е затворен или има повтарящи се дъги; (в) е контур.
Орграф е силно k-свързан: (а) ако е силно свързан за k двойки върха; (б) съответният неориентиран граф е k-свързан; (в) ако за двойка различни върхове v и w поне kнезависими пътя от v до w.
Матрицата на съседствата (аij)за орграф D е квадратна и аij е броят на: (а) дъгите от vi до vj; (б) ребрата между vi и vj; (в)върховете, инцидентни с vi и vj.
Не е вярно, че орграфът е генеалогично дърво, ако: (а)+(v)2, vV, броят на ребрата на всеки редуващ се цикъл е кратен на четири и контур; (б) индивид има най-много двама родители, единият е баща, а другият – майка и никой не може да бъде свой потомък; (в)+(v)=2, vV, броят на ребрата на всеки редуващ се цикъл е четен и контур.
Ако G=(V,E) е свързан ойлеров граф, то: (а) всички върхове имат нечетна степен; (б)Е е цикъл, образуващ единствена минимална реброва факторизация, покриваща G; (в)Е е верига, образуваща единствена минимална реброва факторизация, покриваща G.
Свързаният граф е уникурсален той има: (а) 0 или 2 върха от нечетна степен; (б) 2 върха от нечетна степен; (в) 0 или 2 върха от четна степен.
Хамилтонови верига или цикъл на свързан граф е: (а) елементарна верига или цикъл през всички върхове на графа; (б) верига или цикъл през всички върхове на графа; (в) елементарна верига или цикъл в графа.
Хроматичното число на графа е: (а) най-малкият брой вътрешно устойчиви множества, на които може да се раздели V; (б) най-голямото k, при което графът е k-делен; (в) броят цветове, необходими за оцветяването на върховете така, че два съседни върха да са разноцветни.
Не е вярно, че: (а) поток с големина k е сума от п съгласувани елементарни потоци, k от които са по цикли, а останалите – по вериги; (б) ако е допустим потокс големина k от vW до w=V\W, за произволна факторизация {W,}на V, то ; (в)N(V,A) има капацитет, ако са дадени две целочислени функции и върху А: 0(а)(а), aA.
Теоремата на Кьониг-Хол за сватбите гласи: (а) В пълен двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 ,SV; (б) В двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 ,SV; (в) В двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 , SV.
Формулата на Ойлер за свързан равнинен граф с n върха, m ребра и f области е: (а)n–m+f=2; (б)m–n+f=2; (в)n+m–f=2.
Не е вярно, че: (а) единствените нетривиални правилни многостенни графи са 5; (б) тетраедърът е дуален сам на себе си; (в) кубът е дуален на додекаедъра, а октаедърът – на икосаедъра.
k-оцветяване на върховете на граф G=(V,E) наричаме: (а) функция с: V{1,2,…,k}, такава че множество с–1(j) е вътрешно устойчиво; (б) функция с: V{1,2,…,k}, такава че всички множества с–1(j) са различни; (в) биективна функция с: V{1,2,…,k}.
, (k = сумата от точките)
; (б) m: 0m
; (в) m.
, 
и във Vi (i=1,…k) няма съседни върхове; (б) 
, 
и във Vi (i=1,…k) няма съседни върхове; (в) 
=V\W, за произволна факторизация {W,
; (в) N(V,A) има капацитет, ако са дадени две целочислени функции и върху А: 0(а)(а), aA.
,SV; (б) В двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 
, SV.