Тест №1 по Теория на графите



Дата10.04.2018
Размер66.96 Kb.
#65975


ТЕСТ №1 по Теория на графите



  • Решаването на изпитния тест е в рамките на 60 минути

  • На всеки въпрос е предложен само един правилен отговор

  • Оценяването се извършва по следния начин:

правилен отговор = 2 точки

грешен отговор = – 1 точка

без отговор = 0 точки

Оценка=2+, (k = сумата от точките)




  1. Под граф се разбира: (а) геометрична структура в пространството, състояща се от точки, съе­ди­­не­ни със сис­тема от линейни сегменти; (б) схематично представяне на обекти и отношения между тях; (в) гео­­мет­ри­ч­на фигура, състояща се от точки (наречени върхове) и страни (наречени ребра).

  2. Два графа G=(V,E) и G'=(V',E') са изоморфни един на друг, ако: (а)  изображение на V във V', както и на Е в Е', запазващо инцидентността  ; (б)  взаимно-еднозначно изображение между V и V', меж­ду Е и Е', както и между и ' ; (в)  биекция между V и V', както и между Е и Е', запазваща .

  3. Ако е1(v&w) и е2(v&w), то ребрата е1 и е2 се наричат: (а) примки; (б) паралелни; (в) еднакви.

  4. Прост граф G(n,m) съществува за: (а)m: 0m; (б)m: 0m; (в)m.

  5. Един граф е правилен, ако: (а) върховете и ребрата му са равни на брой; (б) всеки връх е от една и съща степен; (в) степените на върховете са равни на степените на ребрата.

  6. Структурата 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.

  7. Един маршрут е верига или цикъл, ако: (а) е затворен или незатворен; (б) е затворен или незатворен и ос­вен това върховете му са различни; (в) ребрата му са различни.

  8. Не е вярно, че: (а) свързан граф остава свързан след премахване на ребро  това ребро принадлежи на някакъв цикъл; (б) свързан граф с k върха трябва да съдържа поне k –1 ребра; (в)  свързан граф, който става несвързан при премахване на произволно ребро.

  9. Скелет на G се нарича: (а) фактор на G, който е дърво; (б) подграф на G, който е дърво; (в) подграф на G с максимален брой ребра.

  10. В краен правилен граф G от степен h: a)  мост, ако h е нечетно число; (б)  мост, ако h е четно число; (в) може да  мост, ако h е четно число.

  11. През два върха на графа  елементарен цикъл  след премахването на всички късове се получи: (а) ну­лев подграф; (б) ацикличен подграф; (в) подграф с повече от 1 ребро.

  12. Разделящо множество от ребра на граф G: (а) винаги ; (б) , ако има поне 1 мост; (в)  , ако G е пъ­лен.

  13. В свързан граф  затворен маршрут и  ребров разрез: (а) имат четен брой общи ребра; (б) нямат общи ребра; (в) имат нечетен брой общи ребра.

  14. Граф G се нарича k-свързан (k2), когато или G е пълен граф от ред k+1 или: (а) има поне k+2 върха и  множество с най-много k 1 върха, което да е върхов разрез; (б)  множество от поне k 1 върха, което да не е върхов разрез; (в) има поне k+2 върха и  множество с поне k 1 върха, което да е върхов разрез.

  15. Не е вярно, че свързан граф G е 2-реброво свързан, ако: (а) е от ред поне 2-ри; (б) няма ребров разрез от 2 ребра; (в) не съ­държа мост.

  16. Граф G=(V,E) е k-делен, ако: (а) , и във Vi (i=1,…k) няма съседни върхове; (б) , и във Vi (i=1,…k) няма съседни върхове; (в) и във Vi (i=1,…k) няма съседни върхове.

  17. Два ориентирани графа са изоморфни, ако: (а) съответните им неориентирани графи са изоморфни; (б) съответните им неориентирани графи са изоморфни и съответните дъги имат еднаква ори­ен­та­ция; (в) граничните върхове на  две съответни дъги са наредени по един и същ начин.

  18. Ормаршрут не е път, ако: (а) или е затворен или има повтарящи се върхове; (б) или е затворен или има повтарящи се дъги; (в) е контур.

  19. Орграф е силно k-свързан: (а) ако е силно свързан за k двойки върха; (б)  съответният не­ори­ен­ти­ран граф е k-свързан; (в) ако за  двойка различни върхове v и w  поне k независими пътя от v до w.

  20. Матрицата на съседствата ij) за орграф D е квадратна и аij е броят на: (а) дъгите от vi до vj; (б) реб­ра­та между vi и vj; (в) върховете, инцидентни с vi и vj.

  21. Не е вярно, че орграфът е генеалогично дърво, ако: (а) +(v) 2, vV, броят на ребрата на всеки реду­ващ се цикъл е кратен на четири и  контур; (б)  индивид има най-много двама родители, еди­ни­ят е баща, а другият – майка и никой не може да бъде свой потомък; (в) +(v)= 2, vV, броят на реб­рата на всеки редуващ се цикъл е четен и  контур.

  22. Ако G=(V,E) е свързан ойлеров граф, то: (а) всички върхове имат нечетна степен; (б) Е е цикъл, обра­зу­ващ единствена минимална реброва факторизация, покриваща G; (в) Е е верига, образуваща един­стве­на минимална реброва факторизация, покриваща G.

  23. Свързаният граф е уникурсален  той има: (а) 0 или 2 върха от нечетна степен; (б) 2 върха от не­чет­на степен; (в) 0 или 2 върха от четна степен.

  24. Хамилтонови верига или цикъл на свързан граф е: (а) елементарна верига или цикъл през всички вър­х­ове на графа; (б) верига или цикъл през всички върхове на графа; (в) елементарна верига или ци­­къл в графа.

  25. Хроматичното число на графа е: (а) най-малкият брой вътрешно устойчиви множества, на които мо­же да се раздели V; (б) най-голямото k, при което графът е k-делен; (в) броят цветове, необходими за оц­ве­тя­ването на върховете така, че  два съседни върха да са разноцветни.

  26. Не е вярно, че: (а) поток с големина k е сума от п съгласувани елементарни потоци, k от които са по цик­­­ли, а ос­та­на­ли­те – по вериги; (б) ако е допустим поток с големина k от vW до w=V\W, за про­­­из­волна факторизация {W,}на V, то ; (в) N(V,A) има капацитет, ако са дадени две целочислени функции и върху А: 0(а)(а), aA.

  27. Теоремата на Кьониг-Хол за сватбите гласи: (а) В пълен двуделен граф G(V1,V2;Г)  пълно сдвояване на V1 с V2,SV; (б) В двуделен граф G(V1,V2;Г)  пълно сдвояване на V1 с V2,SV; (в) В двуделен граф G(V1,V2;Г)  пълно сдвояване на V1 с V2, SV.

  28. Формулата на Ойлер за свързан равнинен граф с n върха, m ребра и f области е: (а) n  m + f = 2; (б) m  n + f = 2; (в) n + m  f = 2.

  29. Не е вярно, че: (а) единствените нетривиални правилни многостенни графи са 5; (б) тетраедърът е ду­ален сам на себе си; (в) кубът е дуален на додекаедъра, а октаедърът – на икосаедъра.

  30. k-оцветяване на върховете на граф G=(V,E) наричаме: (а) функция с: V{1,2,…,k}, такава че  мно­жест­во с–1(j) е вътрешно устойчиво; (б) функция с: V{1,2,…,k}, такава че всички мно­жест­ва с–1(j) са раз­лич­ни; (в) биективна функция с: V{1,2,…,k}.





Сподели с приятели:




©obuch.info 2023
отнасят до администрацията

    Начална страница