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



страница1/3
Дата19.01.2018
Размер330.63 Kb.
  1   2   3




  • На изпита се дават 30 въпроса от предложените

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

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

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

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

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

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

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




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

  2. Геометричен граф в Е n е множество V от точки в Е n и множество Е от прости линии, удов­лет­во­ря­ва­щи следните условия: (а) 1) всяка затворена линия в Е съдържа една точка от V, 2) всяка незатворена ли­­ния в Е съ­държа поне две точки от V, които са нейни гранични точки, 3) линиите в Е нямат общи точки с из­клю­че­ние на точките от V; (б) 1) всяка затворена линия в Е съдържа само една точка от V, 2) всяка не­за­т­во­­ре­на ли­ния в Е съдържа точно две точки от V, които са нейни гранични точки, 3) лини­и­те в Е мо­же и да нямат общи точки с изключение на точките от V; (в) 1) всяка затворена линия в Е съ­държа са­мо една точка от V, 2) всяка незатворена линия в Е съдържа точно две точки от V, които са ней­ни гра­нич­ни точки, 3) ли­ни­ите в Е нямат общи точки с изключение на точките от V.

  3. Геометричен граф е геометрична структура в Е n, състояща се от множество точки, взаимосвързани чрез: (а) множество от непрекъснати и самонепресичащи се линии; (б) множество от непрекъснати и са­мо­­пре­си­чащи се линии; (в) множество от самонепресичащи се линии.

  4. Граф G е наредената двойка множества (V,E) и изображението инцидентност  , такива че: (а) V, V E=, EV V; (б) V, E, V E=, EV V; (в) V, V E=, EVV.

  5. Графът G=(V,E,) се нарича краен граф, ако (a) е дефинирано върху краен брой елементи; (б) V и E са крайни множества; (в) V или E са крайни множества.

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

  7. Геометрична реализация на графа G се нарича: (а) геометричен граф G', съответен на G; (б) гео­мет­ри­чен граф G', изоморфен на G; (в) геометрично изобразяване на G.

  8. Графът се нарича равнинен, ако: (а) има геометрична реализация в Е 2; (б) върховете му лежат в една рав­нина; (в) върховете и ребрата му лежат в една равнина.

  9. Геометрична реализация в Е 3 има всеки: (а) краен граф; (б) граф от степен 5; (в) краен граф от степен 5.

  10. Графът G=(V,E) има геометрична реализация в Е 3  : (а)  биекция между V и E от една страна и под­мно­жество на R от друга страна; (б)  изоморфен геометричен граф на G в Е 3; (в)  биекция между V и E.

  11. Изоморфизмът между графи: (а) е релация на еквивалентност; (б) е релация на еквивалентност при равнинни графи; (в) не е релация на еквивалентност.

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

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

  14. Върховете v и w са съседни върхове, ако: (а) са съседни елементи във V; (б)  точно 1 ребро е(v&w); (в)  поне 1 ребро е(v&w).

  15. Ребрата е1 и е2 са съседни ребра, ако: (а) имат точно 1 общ край; (б) са съседни елементи във Е; (в) имат поне 1 общ край.

  16. Следното твърдение не е вярно: (а) съседството е отношение между ребра; (б) съседството е отно­ше­ние между върхове; (в) инцидентността е отношение между върхове.

  17. Ред на графа е: (а) броят на ребрата му; (б) размерността му; (в) броят на върховете му.

  18. Размер на графа е: (а) броят на ребрата му; (б) броят на върховете му; (в) сумата от дължините на реб­ра­та му.

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

  20. Не е вярно, че пълният граф има размер: (а) ; (б) ; (в) n2.

  21. Граф, имащ n върха (п>1) и 0 ребра не е: (а) тривиалният граф; (б) нулевият граф; (в) празният граф.

  22. Не е вярно, че: (а) в пълният граф всеки два върха са съседни; (б) в нулевият граф никои два върха не са съседни; (в) тривиалният граф не е едновременно пълен граф от 1-ви ред и нулев граф от 1-ви ред.

  23. Графите G1=(V1,E1) и G2=(V2,E2) са взаимно допълнителни, ако (а) V1V2V, E1 E2= и E1 E2=V&V; (б) E1 E2= и E1 E2=V1&V2; (в) E1 E2= и E1  E2=V&V.

  24. Графите G1=(V1,E1) и G2=(V2,E2), за които V1V2 или E1E2 се наричат: (а) идентични; (б) чужди; (в) раз­­лич­ни.

  25. Степента на върха v е броят на: (а) върховете, съседни на v; (б) върховете, инцидентни с v; (в) ребрата, ин­цидентни с v, плюс удвоения брой на примките във v.

  26. Един връх не е изолиран, когато: (а) степента му е нула; (б) няма съседни върхове; (в) е инцидентен с примка.

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

  28. Не е вярно, че: (а)  пълен граф от ред n е правилен граф от степен (n-1); (б)  правилен граф от сте­пен (n-1) е пълен граф от ред n; (в)  пълен граф от ред n е правилен граф с размер .

  29. Сумата от степените на върховете е равна на: (а) размера на графа; (б) удвоения размер на графа; (в) уд­­воения ред на графа.

  30. Сумата от степените на върховете е: (а) четна; (б) нечетна; (в) нито четна, нито нечетна.

  31. В краен граф: (а) броят на върховете от четна степен е нечетно число; (б) броят на върховете от четна сте­пен е четно число; (в) броят на върховете от нечетна степен е четно число.

  32. Съществува граф с редица от степените на върховете: (а) {2,3,4,4,6,6}; (б) {2,3,3,5,7,8}; (в) {2,3,3,4,7,8}.

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

  34. Фактор на графа G се нарича: (а) всеки подграф на G; (б) подграф на G със същото множество на вър­хо­­ве­те; (в) надграф на G със същото множество на върховете.

  35. Обединение на два графа G1=(V1,E1) и G2=(V2,E2) е граф GG2=(V,E): (а) получен като  връх на G1 е свър­зан чрез ребро с  връх на G2; (б) V=VV2E=ЕЕ2; (в) V=VV2E=ЕЕ2, като освен това  връх на G1 е свързан чрез ребро с  връх на G2.

  36. Обединението на два графа: (а) е подграф на сумата на същите два графа; (б) е допълнителен граф на су­­ма­та на същите два графа; (в) съвпада със сумата на същите два графа.

  37. Чрез отстраняване на ребра можем от  граф да получим: (а) пълен граф; (б) мултиграф; (в) нулев граф.

  38. Прост граф се нарича граф: (а) без паралелни ребра и без примки; (б) без паралелни ребра; (в) без прим­ки.

  39. Чрез отстраняване на ребра можем от  мултиграф да получим: (а) прост граф; (б) граф от по-нисък ред; (в) граф с цикъл.

  40. Маршрут с дължина n се нарича крайна последователност от: (а) n различни ребра за n+1 различни вър­ха на графа; (б) n ребра за n+1 различни върха на графа; (в) n ребра за n+1 върха на графа.

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

  42. Един маршрут може да съдържа: (а) повтарящи се върхове и повтарящи се ребра; (б) само повтарящи се върхове; (в) само повтарящи се ребра.

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

  44. Елементарната верига е верига с: (а) различни върхове, но не непременно различни ребра; (б) различни вър­хове; (в) минимален брой ребра.

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

  46. Не е вярно, че: (а) ако в граф  верига с дължина s, то тя може да бъде продължена до нова верига меж­­ду същите върхове с дължина s+2; (б) между  два различни върха на един граф или  никаква ве­ри­га, или  безброй много вериги; (в) между  два различни върха на един граф  единствена верига с минимална дължина.

  47. Ако в един граф  неелементарна верига между два върха, то: (а)  и поне една елементарна верига между същите върхове; (б)  точно една елементарна верига между същите върхове; (в)  и поне две еле­ментарни вериги между същите върхове.

  48. Не е вярно, че: (а)  неелементарен цикъл може да се раздели на поне два елементарни цикъла; (б)  неелементарна верига може да се раздели на елементарна верига и поне един елементарен цикъл; (в)  неелементарна верига може да се раздели на елементарна верига и точно един елементарен цикъл.

  49. Един граф се нарича свързан граф, ако: (а)  двойка различни върхове, която да може да бъде свързана поне с една верига; (б)  двойка различни върхове може да бъде свързана поне с една верига; (в)  двойка различни върхове може да бъде свързана поне с две вериги.

  50. Компонента на графа G, породена от връх v, се нарича: (а) всички върхове на G, съседни на v; (б) под­граф на G, съдържащ v; (в) подграф на G, съдържащ всички вериги с край v.

  51. Не е вярно, че: (а)  връх определя точно една компонента на графа; (б) две компоненти, породени от два различни върха са или чужди графи или съвпадат; (в)  два различни върха определят две раз­лич­ни компоненти на графа.

  52. Всяка компонента на графа G: (а) може да съдържа изолиран връх на G; (б) е максимален свързан под­граф на G; (в) притежава свързан собствен надграф в G.

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

  54. Цикломатично число на мултиграф G с n върха, m ребра и k компоненти се нарича числото: (а) (G)=  m – n+ p; (б) (G)= n – m+ p; (в) (G) = n – p.

  55. Цикломатичното число на мултиграф G', получен от мултиграфа G чрез добавяне на ново ребро, е: (а) по-голямо с 1 от (G); (б) равно на (G); (в) 0.

  56. Цикломатичното число на мултиграфа G е равно на: (а) най-големият брой независими цикли в G; (б) най-малкият брой независими цикли в G; (в) най-малкият брой зависими цикли в G.

  57. Дърво се нарича: (а) краен свързан граф, имащ поне 2 върха; (б) краен ацикличен граф; (в) краен свър­зан ацикличен граф, имащ поне 2 върха.

  58. Нека G е краен граф от ред п (п  2) със следните свойства: 1. G е свързан и ацикличен; 2. G е свързан и има размер п  1; 3. G е свързан и има размер п  1; 4. G е ацикличен, но добавянето на ребро води до появяването на елементарен цикъл; 5. G е свързан, но губи това свойство при премахване на произ­вол­но ребро; 6.  двойка върхове е съединена с верига, която е единствена. Критериите G да е дърво са: (а) само1., 3., 5.; (б) само 2., 4., 6.; (в) всички.

  59. Всяко дърво от ред п има: (а) поне два висящи върха; (б) точно два висящи върха; (в) п  1 висящи върха.

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

  61. Мост на G се нарича: (а) ребро, чието премахване води до нарушаване свързаността на G; (б) подграф на G, който свързва две компоненти; (в) ребро, което не принадлежи на скелета.

  62. Хорда на G се нарича: (а) ребро, чието премахване води до нарушаване свързаността на G; (б) подграф на G, който свързва две компоненти; (в) ребро, което не принадлежи на скелета.

  63. Не е вярно, че: (а) граф G притежава скелет  G е свързан; (б) ако G е дърво, то той има един скелет, който съвпада с G; (в) скелетът на G е определен еднозначно.

  64. Не е вярно, че броят на скелетите на граф G от ред п е равен на: a) п п – 2 , ако G e пълен граф; (б) мино­ра на произволен елемент от главния диагонал на квадратна матрица (bij) от ред п, където bij = {(vi) при i=j; – 1 при ij и (vi vj) E; 0 при ij и (vi vj) E}, ако G е без примки; (в) по-малкото от двете числа от а) и б).

  65. Не е вярно, че граф G е гора от k дървета, ако: (а) G е ацикличен граф от k компоненти; (б) G е сума от k непресичащи се дървета; (в)  негова компонента е дърво.

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

  67. Върхът v на свързан граф G=(V,E) не е разрязващ връх, ако: (а) подграфът G1[V \ v] е несвързан; (б)  ве­рига, съединяваща  двойка върхове, минава през v; (в) висящ връх.

  68. В граф без съединявания за  елементарна верига  = [v0,v1,…, vk]  елементарни вериги '  и ''  такива, че: (а) '  и ''  са независими, с краища v0 и vk и при движение по '  (или по '') от  v0 към vk индексите на върховете нарастват; (б) '  и ''  са с краища v0 и vk и при движение по '  (или по '') от  v0 към vk индексите на върховете нарастват; (в) '  и ''  са независими, с краища v0 и vk и при движение по '  (или по '') от  v0 към vk индексите на върховете не се повтарят.

  69. В свързан граф без примки за  две ребра е1 и е2: (а)  верига, започваща с е1 и завършваща с е2; (б)  ве­рига, започваща с е1 и завършваща с е2 е елементарна; (в)  елементарна верига, започваща с е1 и завършваща с е2.

  70. В граф без съединявания и без примки: (а)  двойка ребра, през които не минава елементарен цикъл; (б) през произволна двойка ребра минава елементарен цикъл; (в)  двойка ребра, през които да минава еле­ментарен цикъл.

  71. Граф без съединявания и без примки няма разрязващи върхове : (а) няма мостове; (б)  елементарен цикъл през  двойка ребра и през  двойка върхове; (в)  елементарен цикъл през  двойка върхове.

  72. Ако v е разрязващ връх на графа G, а W е компонента, получена след отделянето на v, то къс от G е подграфът G1 на G, породен от: (а) V \ W; (б) W; (в) W {v}.

  73. Късът се присъединява към останалата част от графа чрез: (а) мост;
  1   2   3


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

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