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



Дата30.11.2018
Размер382.5 Kb.
#106789


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



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

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

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

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

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

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

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




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

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

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

  4. Графите 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  3. Теоремата за max поток и min разрез гласи: (а) максималната от големините на потоците от v до w е равна на минималния от капацитетите на разрезите между v и w; (б) минималната от големините на по­тоците от v до w е равна на максималния от капацитетите на разрезите между v и w; (в) мак­си­мал­ният поток от v до w е равен на минималния разрез меж­ду v и w.

  4. Задачата за забранените подграфи е задача от вида: (а) да се определи минималния брой ребра в един п-граф, съдър­жащ граф F; (б) да се определи максималния брой ребра в един п-граф, несъ­дър­жащ граф F; (в) да се определи броя ребра в един п-граф, непринадлежащи на подграф F.

  5. Задачата на Заранкиевич е задача: (а) аналогична на теоремата на Туран в класа на равнинните гра­фи; (б) за определяне на z(m,n;s,t) – максималния брой ребра на двуделен граф с m върха в първия и n вър­ха във втория клас, ако той не съдържа пълен двуделен граф с s върха в първия и t върха във вто­рия клас, където и ; (в) за определяне на z(m,n;s,t) – максималния брой ребра на дву­делен граф с m върха в първия и n вър­ха във втория клас, съдържащ пълен двуделен граф с s вър­ха в първия и t върха във вто­рия клас, където и .

  6. Кое от следните НДУ за равнинност на граф G не е вярно: (а) G не съдържа подграф, изоморфен с точ­ност до връх от степен 2 на един от графите K5 и K3,3; (б) G съдържа база от цикли и един до­пъл­ни­те­лен цикъл, такъв че тази съвкупност от цикли да съдържа точно 2 пъти  ребро на G; (в) G да има спрегнат граф.





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




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

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