Решаването на изпитния тест е в рамките на 60 минути
На всеки въпрос е предложен само един правилен отговор
Оценяването се извършва по следния начин:
правилен отговор = 2 точки
грешен отговор = – 1 точка
без отговор = 0 точки
Оценка=2+, (k=сумата от точките)
Под граф се разбира: (а) геометрична структура в пространството, състояща се от точки, съединени със система от линейни сегменти; (б) схематично представяне на обекти и отношения между тях; (в) геометрична фигура, състояща се от точки (наречени върхове) и страни (наречени ребра).
Геометричен граф в Еn е множество V от точки в Еn и множество Е от прости линии, удовлетворяващи следните условия: (а) 1) всяка затворена линия в Е съдържа една точка от V, 2) всяка незатворена линия в Е съдържа поне две точки от V, които са нейни гранични точки, 3) линиите в Е нямат общи точки с изключение на точките от V; (б) 1) всяка затворена линия в Е съдържа само една точка от V, 2) всяка незатворена линия в Есъдържа точно две точки от V, които са нейни гранични точки, 3) линиите в Е може и да нямат общи точки с изключение на точките от V; (в) 1) всяка затворена линия в Е съдържа само една точка от V, 2) всяка незатворена линия в Е съдържа точно две точки от V, които са нейни гранични точки, 3) линиите в Е нямат общи точки с изключение на точките от V.
Геометричен граф е геометрична структура в Еn, състояща се от множество точки, взаимосвързани чрез: (а) множество от непрекъснати и самонепресичащи се линии; (б) множество от непрекъснати и самопресичащи се линии; (в) множество от самонепресичащи се линии.
Граф G е наредената двойка множества (V,E) и изображението инцидентност , такива че: (а)V, V E=, EV V; (б) V, E, V E=, EV V; (в)V, V E=, EVV.
Графът G=(V,E,) се нарича краен граф, ако (a)е дефинирано върху краен брой елементи; (б) V и E са крайни множества; (в)V или E са крайни множества.
Два графа G=(V,E) и G'=(V',E') са изоморфни един на друг, ако: (а) изображение на V във V', както и на Е в Е', запазващо инцидентността ; (б) взаимно-еднозначно изображение между V и V', между Е и Е', както и между и'; (в) биекция между V и V', както и между Е и Е', запазваща .
Геометрична реализация на графа G се нарича: (а) геометричен граф G', съответен на G; (б) геометричен граф G', изоморфен на G; (в) геометрично изобразяване на G.
Графът се нарича равнинен, ако: (а) има геометрична реализация в Е2; (б) върховете му лежат в една равнина; (в) върховете и ребрата му лежат в една равнина.
Геометрична реализация в Е3 има всеки: (а) краен граф; (б) граф от степен 5; (в) краен граф от степен 5.
Графът G=(V,E) има геометрична реализация в Е3 : (а) биекция между V и E от една страна и подмножество на R от друга страна; (б) изоморфен геометричен граф на G в Е3; (в) биекция между V и E.
Изоморфизмът между графи: (а) е релация на еквивалентност; (б) е релация на еквивалентност при равнинни графи; (в) не е релация на еквивалентност.
Два графа не могат да бъдат изоморфни, ако: (а) единият е равнинен, а другият не е; (б) броят на върховете и ребрата им не е един и същ; (в) броят на върховете (съотв. ребрата) на единия не е равен на броя на върховете (съотв. ребрата) на другия.
Ако е1(v&w) и е2(v&w), то ребрата е1 и е2 се наричат: (а) примки; (б) паралелни; (в) еднакви.
Върховете v и w са съседни върхове, ако: (а) са съседни елементи във V; (б) точно 1 ребро е(v&w); (в) поне 1 ребро е(v&w).
Ребрата е1 и е2 са съседни ребра, ако: (а) имат точно 1 общ край; (б) са съседни елементи във Е; (в) имат поне 1 общ край.
Следното твърдение не е вярно: (а) съседството е отношение между ребра; (б) съседството е отношение между върхове; (в) инцидентността е отношение между върхове.
Ред на графа е: (а) броят на ребрата му; (б) размерността му; (в) броят на върховете му.
Размер на графа е: (а) броят на ребрата му; (б) броят на върховете му; (в) сумата от дължините на ребрата му.
Прост граф G(n,m) съществува за: (а) m: 0m; (б) m: 0m; (в) m.
Не е вярно, че пълният граф има размер: (а); (б); (в)n2.
Граф, имащ n върха (п>1) и 0 ребра не е: (а) тривиалният граф; (б) нулевият граф; (в) празният граф.
Не е вярно, че: (а) в пълният граф всеки два върха са съседни; (б) в нулевият граф никои два върха не са съседни; (в) тривиалният граф не е едновременно пълен граф от 1-ви ред и нулев граф от 1-ви ред.
Графите G1=(V1,E1) и G2=(V2,E2) са взаимно допълнителни, ако (а)V1V2V, E1E2= и E1E2=V&V; (б) E1E2= и E1E2=V1&V2; (в)E1E2= и E1 E2=V&V.
Графите G1=(V1,E1) и G2=(V2,E2), за които V1V2 или E1E2 се наричат: (а) идентични; (б) чужди; (в) различни.
Степента на върха v е броят на: (а) върховете, съседни на v; (б) върховете, инцидентни с v; (в) ребрата, инцидентни с v, плюс удвоения брой на примките във v.
Един връх не е изолиран, когато: (а) степента му е нула; (б) няма съседни върхове; (в) е инцидентен с примка.
Един граф е правилен, ако: (а) върховете и ребрата му са равни на брой; (б) всеки връх е от една и съща степен; (в) степените на върховете са равни на степените на ребрата.
Не е вярно, че: (а) пълен граф от ред n е правилен граф от степен (n-1); (б) правилен граф от степен (n-1) е пълен граф от ред n; (в) пълен граф от ред n е правилен граф с размер .
Сумата от степените на върховете е равна на: (а) размера на графа; (б) удвоения размер на графа; (в) удвоения ред на графа.
Сумата от степените на върховете е: (а) четна; (б) нечетна; (в) нито четна, нито нечетна.
В краен граф: (а) броят на върховете от четна степен е нечетно число; (б) броят на върховете от четна степен е четно число; (в) броят на върховете от нечетна степен е четно число.
Съществува граф с редица от степените на върховете: (а) {2,3,4,4,6,6}; (б) {2,3,3,5,7,8}; (в) {2,3,3,4,7,8}.
Структурата 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.
Фактор на графа G се нарича: (а) всеки подграф на G; (б) подграф на G със същото множество на върховете; (в) надграф на G със същото множество на върховете.
Обединение на два графа G1=(V1,E1) и G2=(V2,E2) е граф G1 G2=(V,E): (а) получен като връх на G1е свързан чрез ребро с връх на G2; (б)V=V1 V2 E=Е1 Е2; (в)V=V1 V2 E=Е1 Е2, като освен това връх на G1е свързан чрез ребро с връх на G2.
Обединението на два графа: (а) е подграф на сумата на същите два графа; (б) е допълнителен граф на сумата на същите два графа; (в) съвпада със сумата на същите два графа.
Чрез отстраняване на ребра можем от граф да получим: (а) пълен граф; (б) мултиграф; (в) нулев граф.
Прост граф се нарича граф: (а) без паралелни ребра и без примки; (б) без паралелни ребра; (в) без примки.
Чрез отстраняване на ребра можем от мултиграф да получим: (а) прост граф; (б) граф от по-нисък ред; (в) граф с цикъл.
Маршрут с дължина n се нарича крайна последователност от: (а)n различни ребра за n+1 различни върха на графа; (б)n ребра за n+1 различни върха на графа; (в)n ребра за n+1 върха на графа.
Маршрутите се делят на затворени и незатворени според това дали: (а) първият и последният им връх съвпадат или не; (б) затварят или не други върхове на графа; (в) маршрутът съдържа краен или безкраен брой върхове.
Един маршрут може да съдържа: (а) повтарящи се върхове и повтарящи се ребра; (б) само повтарящи се върхове; (в) само повтарящи се ребра.
Един маршрут е верига или цикъл, ако: (а) е затворен или незатворен; (б) е затворен или незатворен и освен това върховете му са различни; (в) ребрата му са различни.
Елементарната верига е верига с: (а) различни върхове, но не непременно различни ребра; (б) различни върхове; (в) минимален брой ребра.
Елементарният цикъл е: (а) примка; (б) затворен маршрут с различни върхове; (в) с геометрична реализация проста незатворена линия.
Не е вярно, че: (а) ако в граф верига с дължина s, то тя може да бъде продължена до нова верига между същите върхове с дължина s+2; (б) между два различни върха на един граф или никаква верига, или безброй много вериги; (в) между два различни върха на един граф единствена верига с минимална дължина.
Ако в един граф неелементарна верига между два върха, то: (а) и поне една елементарна верига между същите върхове; (б) точно една елементарна верига между същите върхове; (в) и поне две елементарни вериги между същите върхове.
Не е вярно, че: (а) неелементарен цикъл може да се раздели на поне два елементарни цикъла; (б) неелементарна верига може да се раздели на елементарна верига и поне един елементарен цикъл; (в) неелементарна верига може да се раздели на елементарна верига и точно един елементарен цикъл.
Един граф се нарича свързан граф, ако: (а) двойка различни върхове, която да може да бъде свързана поне с една верига; (б) двойка различни върхове може да бъде свързана поне с една верига; (в) двойка различни върхове може да бъде свързана поне с две вериги.
Компонента на графа G, породена от връх v, се нарича: (а) всички върхове на G, съседни на v; (б) подграф на G, съдържащ v; (в) подграф на G, съдържащ всички вериги с край v.
Не е вярно, че: (а) връх определя точно една компонента на графа; (б) две компоненти, породени от два различни върха са или чужди графи или съвпадат; (в) два различни върха определят две различни компоненти на графа.
Всяка компонента на графа G: (а) може да съдържа изолиран връх на G; (б) е максимален свързан подграф на G; (в) притежава свързан собствен надграф в G.
Не е вярно, че: (а) свързан граф остава свързан след премахване на ребро това ребро принадлежи на някакъв цикъл; (б) свързан граф с k върха трябва да съдържа поне k –1 ребра; (в) свързан граф, който става несвързан при премахване на произволно ребро.
Цикломатично число на мултиграф G с n върха, m ребра и k компоненти се нарича числото: (а)(G)= m– n+p; (б) (G)=n– m+p; (в) (G) =n– p.
Цикломатичното число на мултиграф G', получен от мултиграфа G чрез добавяне на ново ребро, е: (а) по-голямо с 1 от (G); (б) равно на (G); (в) 0.
Цикломатичното число на мултиграфа G е равно на: (а) най-големият брой независими цикли в G; (б) най-малкият брой независими цикли в G; (в) най-малкият брой зависими цикли в G.
Нека G е краен граф от ред п (п2) със следните свойства: 1.G е свързан и ацикличен; 2.G е свързан и има размер п–1; 3.G е свързан и има размер п–1; 4.G е ацикличен, но добавянето на ребро води до появяването на елементарен цикъл; 5.G е свързан, но губи това свойство при премахване на произволно ребро; 6. двойка върхове е съединена с верига, която е единствена. Критериите G да е дърво са: (а) само1., 3., 5.; (б) само 2., 4., 6.; (в) всички.
Всяко дърво от ред п има: (а) поне два висящи върха; (б) точно два висящи върха; (в) п–1 висящи върха.
Скелет на G се нарича: (а) фактор на G, който е дърво; (б) подграф на G, който е дърво; (в) подграф на G с максимален брой ребра.
Мост на G се нарича: (а) ребро, чието премахване води до нарушаване свързаността на G; (б) подграф на G, който свързва две компоненти; (в) ребро, което не принадлежи на скелета.
Хорда на G се нарича: (а) ребро, чието премахване води до нарушаване свързаността на G; (б) подграф на G, който свързва две компоненти; (в) ребро, което не принадлежи на скелета.
Не е вярно, че: (а) граф G притежава скелет G е свързан; (б) ако G е дърво, то той има един скелет, който съвпада с G; (в) скелетът на G е определен еднозначно.
Не е вярно, че броят на скелетите на граф G от ред п е равен на: a)п п– 2 , ако G e пълен граф; (б) минора на произволен елемент от главния диагонал на квадратна матрица (bij) от ред п, където bij = {(vi) при i=j; –1 при ij и (vi vj)E; 0 при ij и (vi vj)E}, ако G е без примки; (в) по-малкото от двете числа от а) и б).
Не е вярно, че граф G е гораот k дървета, ако: (а)G е ацикличен граф от k компоненти; (б)G е сума от k непресичащи се дървета; (в) негова компонента е дърво.
В краен правилен граф G от степен h: a) мост, ако h е нечетно число; (б) мост, ако h е четно число; (в) може да мост, ако h е четно число.
Върхът v на свързан граф G=(V,E) не е разрязващ връх, ако: (а) подграфът G1[V\v] е несвързан; (б) верига, съединяваща двойка върхове, минава през v; (в) висящ връх.
В граф без съединявания за елементарна верига =[v0,v1,…, vk] елементарни вериги ' и '' такива, че: (а)' и '' са независими, с краища v0 и vkи при движение по ' (или по '') от v0 към vk индексите на върховете нарастват; (б)' и '' са с краища v0 и vkи при движение по ' (или по '') от v0 към vk индексите на върховете нарастват; (в)' и '' са независими, с краища v0 и vkи при движение по ' (или по '') от v0 към vk индексите на върховете не се повтарят.
В свързан граф без примки за две ребра е1 и е2: (а) верига, започваща с е1 и завършваща с е2; (б) верига, започваща с е1 и завършваща с е2 е елементарна; (в) елементарна верига, започваща с е1 и завършваща с е2.
В граф без съединявания и без примки: (а) двойка ребра, през които не минава елементарен цикъл; (б) през произволна двойка ребра минава елементарен цикъл; (в) двойка ребра, през които да минава елементарен цикъл.
Граф без съединявания и без примки няма разрязващи върхове : (а) няма мостове; (б) елементарен цикъл през двойка ребра и през двойка върхове; (в) елементарен цикъл през двойка върхове.
Ако v е разрязващ връх на графа G, а W е компонента, получена след отделянето на v, то къс от G е подграфът G1 на G, породен от: (а) V\W; (б) W; (в) W{v}.
Късът се присъединява към останалата част от графа чрез: (а) мост;
, (k = сумата от точките)
; (б) m: 0m
; (в) m.
; (б)