Решаването на изпитния тест е в рамките на 60 минути
На всеки въпрос е предложен само един правилен отговор
Оценяването се извършва по следния начин:
правилен отговор = 2 точки
грешен отговор = – 1 точка
без отговор = 0 точки
Оценка=2+, (k=сумата от точките)
Геометричен граф е геометрична структура в En, състояща се от множество точки, взаимосвързани чрез: (а) множество от непрекъснати и самонепресичащи се линии; (б) множество от непрекъснати и самопресичащи се линии; (в) множество от самонепресичащи се линии.
Два графа не могат да бъдат изоморфни, ако: (а) единият е равнинен, а другият не е; (б) броят на върховете и ребрата им не е един и същ; (в) броят на върховете (съотв. ребрата) на единия не е равен на броя на върховете (съотв. ребрата) на другия.
Ребрата е1 и е2 са съседни ребра, ако: (а) имат точно 1 общ край; (б) са съседни елементи във Е; (в) имат поне 1 общ край.
Графите G1=(V1,E1) и G2=(V2,E2) са взаимно допълнителни, ако (а)V1V2V, E1E2= и E1E2=V&V; (б) E1E2= и E1E2=V1&V2; (в)E1E2= и E1 E2=V&V.
Не е вярно, че: (а) пълен граф от ред n е правилен граф от степен (n-1); (б) правилен граф от степен (n-1) е пълен граф от ред n; (в) пълен граф от ред n е правилен граф с размер .
В краен граф: (а) броят на върховете от четна степен е нечетно число; (б) броят на върховете от четна степен е четно число; (в) броят на върховете от нечетна степен е четно число.
Фактор на графа 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.; (в) всички.
Мост на G се нарича: (а) ребро, чието премахване води до нарушаване свързаността на G; (б) подграф на G, който свързва две компоненти; (в) ребро, което не принадлежи на скелета.
Върхът v на свързан граф G=(V,E) не е разрязващ връх, ако: (а) подграфът G1[V\v] е несвързан; (б) верига, съединяваща двойка върхове, минава през v; (в) висящ връх.
Подмножеството от ребра на свързан граф G=(V,E) се нарича разделящо множество от ребра, ако: (а) подграфът G' =(V,E\F) е свързан; (б) подграфът G' =(V,E\F) не е свързан; (в) подграф G' =(V,E\F).
Елементарен ребров разрез е: (а) ребров разрез, делящ графа точно на две компоненти; (б) ребров разрез, делящ графа поне на две компоненти; (в) разрез от 1 ребро.
Ако W е множество от върхове на G, чието отстраняване заедно с инцидентните им ребра, води до разпадане на G на компоненти, то W е: (а) минимален върхов разрез на G; (б) множество на изолация в G; (в) върхов разрез на G.
Граф G е k-реброво свързан (k2), ако G има поне 2 върха и: (а) никое подмножество на Е от най-много k–1 ребра да не е ребров разрез; (б) никое подмножество на Е от най-малко k–1 ребра да не е ребров разрез; (в) подмножество на Е от k+1 ребра, което да е ребров разрез.
Не е вярно, че свързан граф G е 2-свързан, ако: (а) е от ред поне 4-ти; (б) е пълен граф от ред 4-ти; (в) не съдържа разрязващ връх.
В 2-делен граф може да: (а) се съдържа триъгълник С3 като подграф; (б) има връх от V1, съседен на всеки връх от V; (в) има връх от V1, съседен на всеки връх от V2.
За два изоморфни ориентирани графа D и D'не е вярно, че: (а)D (съотв. D') е равнинен съответния му неориентиран граф е равнинен; (б) съответните на D и D' неориентирани графи са изоморфни; (в) съответните на D и D' неориентирани графи може и да не са изоморфни.
Ормаршрут е контур, ако: (а) или е затворен или има повтарящи се върхове; (б) е затворен и няма повтарящи се дъги; (в) или е незатворен или няма повтарящи се дъги.
За ориентирано дърво Т с корен v0не е вярно, че: (а)Т е дърво в неориентиран смисъл и единствената верига между v0 и друг връх w е път от v0 до w; (б)Т е симетричен орграф; (в)+(vi)=1, viv0, +(v0)=0 и контур в Т.
Матрицата на съседствата не се използва при: (а) преброяване на пътища със зададени условия; (б) задачата за лидера; (в) задачата на Ойлер за кьонигсбергските мостове.
Уникурсален граф е този, в който: (а) реброва факторизация е верига или цикъл; (б) единствен контур; (в) реброва факторизация от една верига или един цикъл.
Ориентиран свързан граф е уникурсален (а) той е или ориентиран ойлеров граф или такъв, че има само два върха, в които разликата между + и – е единица; (б) той е ориентиран ойлеров граф; (в) той е или ориентиран ойлеров граф или такъв, че има само два неравновесни върха.
Хамилтонов път във : (а) несвързан антисиметричен граф; (б) пълен контурен граф; (в) пълен антисиметричен граф.
Не евярно, че за максимално вътрешно устойчиво множество (макс.Вътр.УМ) и за доминиращо множество (ДМ) имаме: (а) макс.вътр.УМ е ДМ; (б) мощността на макс.вътр.УМ мощността на минималното ДМ; (в) допълнението на макс.вътр.УМ е също макс.Вътр.УМ.
За дърво на най-късите разстояния Т относно v0е вярно, че: (а) единственият път от v0до wv0на Т е най-късият път от v0до w; (б) за хорда (v,w), v,wТ, разстоянието по Т от v0до w е най-малко разстоянието по Т от v0до v плюс дължината на (v,w); (в)Т е единственото ориентирано дърво с корен v0 с тези свойства.
Теоремата за max поток и min разрез гласи: (а) максималната от големините на потоците от v до w е равна на минималния от капацитетите на разрезите между v и w; (б) минималната от големините на потоците от v до w е равна на максималния от капацитетите на разрезите между v и w; (в) максималният поток от v до w е равен на минималния разрез между v и w.
Задачата за забранените подграфи е задача от вида: (а) да се определи минималния брой ребра в един п-граф, съдържащ граф F; (б) да се определи максималния брой ребра в един п-граф, несъдържащ граф F; (в) да се определи броя ребра в един п-граф, непринадлежащи на подграф F.
Задачата на Заранкиевич е задача: (а) аналогична на теоремата на Туран в класа на равнинните графи; (б) за определяне на z(m,n;s,t) – максималния брой ребра на двуделен граф с m върха в първия и n върха във втория клас, ако той не съдържа пълен двуделен граф с s върха в първия и t върха във втория клас, където и ; (в) за определяне на z(m,n;s,t) – максималния брой ребра на двуделен граф с m върха в първия и n върха във втория клас, съдържащ пълен двуделен граф с s върха в първия и t върха във втория клас, където и .
Кое от следните НДУ за равнинност на граф Gне е вярно: (а)G не съдържа подграф, изоморфен с точност до връх от степен 2 на един от графите K5и K3,3; (б)G съдържа база от цикли и един допълнителен цикъл, такъв че тази съвкупност от цикли да съдържа точно 2 пъти ребро на G; (в)G да има спрегнат граф.