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



страница2/3
Дата30.11.2018
Размер0.69 Mb.
#106788
1   2   3
(а) мост; (б) разрязващ връх; (в) цикъл.

  •  къс на графа: (а) не може да съдържа други късове; (б) може да съдържа по-малки късове; (в) не може да съдържа по-големи късове.

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

  • Подмножеството от ребра на свързан граф G=(V,E) се нарича разделящо множество от ребра, ако: (а) под­графът G' =(V, E \ F) е свързан; (б) подграфът G' =(V, E \ F) не е свързан; (в)  подграф G' =(V, E \ F).

  • Разделящо множество от ребра на граф може да се състои от: (а) поне 2 ребра; (б) 1 мост; (в) поне 1 раз­ряз­ващ връх.

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

  • Ако за свързан граф G=(V,E) множеството V е разделено на две непразни допълващи се подмножества V1 и V2, то ребров разрез е: (а) наредената двойка (V1,V2); (б) подграфът G'[V1] или G''[V2]; (в) мно­жест­во­то от реб­рата, съединяващи V1 и V2.

  • Елементарен ребров разрез е: (а) ребров разрез, делящ графа точно на две компоненти; (б) ребров раз­рез, делящ графа поне на две компоненти; (в) разрез от 1 ребро.

  •  скелет на графа: (а) не съдържа общи ребра с произволен ребров разрез на графа; (б) има поне 1 общо реб­ро с произволен ребров разрез на графа; (в) съвпада с максимален ребров разрез на графа.

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

  • Степен на реброва свързаност за ребров разрез между две непразни допълващи се подмножества V1 и V2 на V за G=(V,E) е: (а) броят на елементарните реброви разрези между V1 и V2; (б) броят на мостовете между V1 и V2; (в) броят на ребрата на елементарните реброви разрези между V1 и V2.

  • Степен на реброва свързаност на граф G е: (а) броят на всички елементарни реброви разрези в G; (б) ми­ни­малното число от всички степени на реброва свързаност за всички елементарни реброви разрези в G; (в) минималното брой елементарни реброви разрези в G.

  • Подмножеството W от върхове на свързан граф G=(V,E) е разделящо множество от върхове, ако: (а) под­графът G' =(V,E \ W) не е свързан; (б) подграфът G'[V \ W] не е свързан; (в) W съдържа поне 1 връх.

  • Ако W е множество от върхове на G, чието отстраняване заедно с инцидентните им ребра, води до раз­па­дане на G на компоненти, то W е: (а) минимален върхов разрез на G; (б) множество на изолация в G; (в) върхов разрез на G.

  • Степен на върхова свързаност на върхов разрез на граф G е броят на: (а) върховете на върхов разрез на G; (б) върховете на елементарен върхов разрез на G; (в) разрязващите върхове на G.

  • Степен на върхова свързаност на граф G е: (а) минималната степен на върхова свързаност за всички раз­­рези на G; (б) максималната степен на върхова свързаност за всички разрези на G; (в) броят на всич­ки върхови разрези на G.

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

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

  • Свързаност на G е: (а) минималната стойност на k, за която свързаният граф G е k-свързан; (б) стойност на k, за която свързаният граф G е k-реброво свързан; (в) максималната стойност на k, за която свър­за­ни­ят граф G е k-свързан.

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

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

  • Ако G е нетривиален от степен , с реброва свързаност и свързаност æ, то имаме: (а)  æ; (б) æ<< ; (в) æ  .

  • Ако G е k-свързан граф от ред п, то G е свързан и освен това: (а) k<п и няма разрез с по-малко от k еле­мен­та; (б) k<п –2 и няма разрез с по-малко от k елемента; (в) k<п и няма разрез от k елемента.

  • В k-свързан граф: (а) степента на всеки връх е поне k; (б) степента на всеки връх е най-много k; (в) бро­ят на ребрата, инцидентни с всеки връх е k.

  • Граф G е k-свързан   два върха могат да се съединят с: (а) k различни независими елементарни цикли; (б) k различни независими елементарни вериги; (в) k различни елементарни вериги.

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

  • В 2-делен граф може да: (а) се съдържа триъгълник С3 като подграф; (б) има връх от V1, съседен на все­ки връх от V; (в) има връх от V1, съседен на всеки връх от V2.

    1. Пълен k-делен граф е k-делен граф, за който: (а)  връх от Vi e съседен на  връх от Vj (1 i j k); (б)  връх от Vi e съседен на  връх от V(1 i  k); (в)  два върха от V са съседни.

    2. За пълния 2-делен граф Kp,q не е вярно, че: (а) Kp,q е правилен, когато p=q; (б) размерът на Kp,q е най-малко p+q –1; (в) размерът на Kp,q е p+q.

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

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

    5. За два изоморфни ориентирани графа D и D' не е вярно, че: (а) D (съотв. D' ) е равнинен  съ­от­вет­ния му неориентиран граф е равнинен; (б) съответните на D и D' неориентирани графи са изо­морф­ни; (в) съ­ответните на D и D' неориентирани графи може и да не са изоморфни.

    6. За дъги, ориентирани от v към w, е вярно, че: (а) те са строго паралелни,  от тях е положително ин­ци­­дент­на с w и отрицателно инцидентна с v и броят на положително (съотв. отрицателно) инци­дент­ни­те дъ­ги е положителна (съотв. отрицателна) полустепен на върха; (б) те са нестрого паралелни,  от тях е от­рицателно ин­ци­дент­на с w и по­ложително инцидентна с v и броят на положително (съотв. от­­ри­ца­тел­но) инцидентните дъ­ги е положителна (съотв. отрицателна) полустепен на върха; (в) те са стро­го па­ралелни,  от тях е отрицателно ин­ци­дент­на с w и положително инцидентна с v и броят на по­­ло­­жи­тел­но (съотв. отриц.) инцидентните дъ­ги е положителна (съотв. отриц.) полустепен на вър­ха.

    7. Сумата на положителните полустепени на всички върхове и сумата на отрицателните полу­сте­пени на всички върхове: (а) са равни на броят на върховете; (б) са равни на броят на ребрата; (в) не са рав­ни.

    8. За орграфа D и съответния му неориентиран граф G имаме: (а) ако G не е прост, то D има строго па­ра­­­лел­ни дъги; (б) ако G е прост, то може D да не е прост орграф; (в) ако D е прост орграф и има не­стро­го па­ра­­лел­ни дъги, то G не е прост неориентиран граф.

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

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

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

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

    13. Орграф е силно свързан, ако: (а)  двойка различни върхове v и w, за които  път от v до w и път от w до v; (б) за  двойка различни върхове v и w  път от v до w и път от w до v; (в) за  двойка различни върхове v и w  път от v до w.

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

    15. За симетричния орграф D=(V,A) не е вярно, че: (а) ако (v,w)А, то и (w,v)А; (б) ако (v,w)А, то (w,v)А; (в) D е изоморфен на съответния неориентиран граф.

    16. За ориентирано дърво Т с корен v0 не е вярно, че: (а) Т е дърво в неориентиран смисъл и един­стве­на­та верига между v0­­­ и  друг връх w е път от v0­­­ до w; (б) Т е симетричен орграф; (в) +( vi )=1,  vi v0, +( v0 )=0 и  контур в Т.

    17. Ако D е силно свързан, двата ориентирани дъгови разреза за произволна върхова факторизация {W,W'}: (а) може да са празни; (б) са с равна мощност; (в) прекъсват пътищата от W към W' и обратно.

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

    19. За орграф D и неговата матрица на съседствата ij) не е вярно, че: (а) D е симетричен  аij  аji; (б) D е антисиметричен  аijji1; (в) D е пълен  аijji1.

    20. Матрицата на съседствата не се използва при: (а) преброяване на пътища със зададени условия; (б) задачата за лидера; (в) задачата на Ойлер за кьонигсбергските мостове.

    21. Не е вярно, че: (а) матрицата на инцидентностите на ребрата е напълно унимодуларна  графът е двуделен; (б) матрицата на инцидентностите на ребрата е напълно унимодуларна; (в) матрицата на инцидентностите на дъгите е напълно унимодуларна.

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

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

    24. Уникурсален граф е този, в който: (а)  реброва факторизация е верига или цикъл; (б)  единствен кон­тур; (в)  реброва факторизация от една верига или един цикъл.

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

    26. Ако G е свързан граф с 2п върха от нечетна степен, то  минимална реброва факторизация се състои от: (а) п вериги,  от които съединява два върха от нечетна степен; (б) п цикли,  от които съе­ди­ня­ва два върха от нечетна степен; (в) п вериги,  от които съединява два върха от четна степен.

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

    28. Ориентиран ойлеров граф е орграф, за който: (а)  +(v)+ –(v)=0, v; (б)  +(v)= –(v) за v; (в) (v) е четно за v.

    29. В ориентиран ойлеров граф D=(V,A) множеството А не представлява: (а) контур; (б) минимална дъ­го­ва факто­ри­за­ция; (в) максимален дъгов разрез.

    30. Ориентиран свързан граф е уникурсален  (а) той е или ориентиран ойлеров граф или такъв, че има са­мо два върха, в които разликата между  + и  – е единица; (б) той е ориентиран ойлеров граф; (в) той е или ориентиран ойлеров граф или такъв, че има само два неравновесни върха.

    31. Свързан граф G е ориентируем като силно свързан орграф D  : (а) G е ойлеров; (б)  ребро на G при­над­ле­жи на поне един цикъл; (в) D е симетричен.

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

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

    34. Хамилтонов път  във : (а) несвързан антисиметричен граф; (б) пълен контурен граф; (в) пълен антисиметричен граф.

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

    36. Подмножество S на V е вътрешно устойчиво множество, ако: (а) S не съдържа два съседни върха; (б)  връх от допълнението на S е съседен на негов връх; (в) S не съдържа два несъседни върха.

    37. Не е вярно, че за максимално вътрешно устойчиво множество (макс.Вътр.УМ) и за доминиращо мно­жес­т­во (ДМ) имаме: (а) макс.вътр.УМ е ДМ; (б) мощ­ността на макс.вътр.УМ  мощността на мини­мал­ното ДМ; (в) допълнението на макс.вътр.УМ е също макс.Вътр.УМ.

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

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

    40. Ако графът G е бихроматичен, то G: (а) не съдържа цикли с нечетна дължина; (б) е дърво; (в) не е 2-делен.

    41. За вътрешно устойчиво множество (Вътр.УМ) на G не е вярно, че: (а) броят върхове на най-голямо­то Вътр.УМ е числото на вътрешната устойчивост на G; (б) произведението на числото на вът­реш­на­та ус­тойчивост и хроматичното число е най-много реда на G; (в)  подмножество на Вътр.УМ, което не е Вътр. УМ.

    42. Подмножество от върхове Т  V е външно устойчиво множество на графа G=(V,E), ако: (а) за  vT wT : (v&w)E; (б) vT : wT, (v&w)E; (в) за  vT, wT : (v&w)E.

    43. Не е вярно, че: (а) числото на външната устойчивост на графа G=(V,E) е минималната мощност из­меж­ду вън­шно устойчивите множества (ВнУМ) на G; (б) V е ВнУМ; (в)  подмножество на ВнУМ е също ВнУМ.

    44. Не е вярно, че: (а) отдалеченост на връх v е максималният брой ребра в най-късата верига между v и  друг връх; (б) център на G е върхът с минимална отдалеченост от  друг връх, а радиус на G е от­да­лечеността на центъра в G; (в) диаметърът на G е максималният брой ребра в най-късата верига между  два върха в G и диаметърът на G е равен на два пъти радиуса на G.

    45. За дърво на най-късите разстояния Т относно v0 е вярно, че: (а) един­стве­ният път от v0 до  wv0 на Т е най-късият път от v0 до w; (б) за  хорда (v,w), v,wТ, раз­стоянието по Т от v0 до w е най-малко раз­сто­­я­ни­ето по Т от v0 до v плюс дължината на (v,w); (в) Т е единственото ориентирано дърво с корен v0 с тези свойства.

    46. За мрежа N(V,A) е вярно: (а) чист поток през v в N е разликата между сумата от потоците по в­ли­за­щи­те дъги във v и сумата от потоците по излизащите дъги от v; (б) потокът е ограничен от по­то­ците 1 и 2, ако големината на по aA е между големините на 1 и 2 по aA; (в) по­то­ците 1 и 2 са съгласувани, ако произведението на тези потоци по aA е отрицателно число.

    47. Не е вярно, че:


      Сподели с приятели:
  • 1   2   3




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

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