къс на графа: (а) не може да съдържа други късове; (б) може да съдържа по-малки късове; (в) не може да съдържа по-големи късове.
През два върха на графа елементарен цикъл след премахването на всички късове се получи: (а) нулев подграф; (б) ацикличен подграф; (в) подграф с повече от 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.
Пълен k-делен граф е k-делен граф, за който: (а) връх от Vie съседен на връх от Vj(1ijk); (б) връх от Vie съседен на връх от V(1i k); (в) два върха от V са съседни.
За пълния 2-делен граф Kp,qне е вярно, че: (а)Kp,q е правилен, когато p=q; (б)размерът на Kp,q е най-малко p+q –1; (в) размерът на Kp,q е p+q.
Ориентираният граф се различава от неориентирания по това, че в орграфа: (а) върховете на ребро образуват наредена двойка; (б) върховете на ребро образуват ненаредена двойка; (в) има път между два върха.
Два ориентирани графа са изоморфни, ако: (а) съответните им неориентирани графи са изоморфни; (б) съответните им неориентирани графи са изоморфни и съответните дъги имат еднаква ориентация; (в) граничните върхове на две съответни дъги са наредени по един и същ начин.
За два изоморфни ориентирани графа D и D'не е вярно, че: (а)D (съотв. D') е равнинен съответния му неориентиран граф е равнинен; (б) съответните на D и D' неориентирани графи са изоморфни; (в) съответните на D и D' неориентирани графи може и да не са изоморфни.
За дъги, ориентирани от v към w, е вярно, че: (а) те са строго паралелни, от тях е положително инцидентна с w и отрицателно инцидентна с v и броят на положително (съотв. отрицателно) инцидентните дъги е положителна (съотв. отрицателна) полустепен на върха; (б) те са нестрого паралелни, от тях е отрицателно инцидентна с w и положително инцидентна с v и броят на положително (съотв. отрицателно) инцидентните дъги е положителна (съотв. отрицателна) полустепен на върха; (в) те са строго паралелни, от тях е отрицателно инцидентна с w и положително инцидентна с v и броят на положително (съотв. отриц.) инцидентните дъги е положителна (съотв. отриц.) полустепен на върха.
Сумата на положителните полустепени на всички върхове и сумата на отрицателните полустепени на всички върхове: (а) са равни на броят на върховете; (б) са равни на броят на ребрата; (в) не са равни.
За орграфа D и съответния му неориентиран граф Gимаме: (а) ако G не е прост, то D има строго паралелни дъги; (б) ако G е прост, то може D да не е прост орграф; (в) ако D е прост орграф и има нестрого паралелни дъги, то G не е прост неориентиран граф.
Ормаршрут не е път, ако: (а) или е затворен или има повтарящи се върхове; (б) или е затворен или има повтарящи се дъги; (в) е контур.
Ормаршрут е контур, ако: (а) или е затворен или има повтарящи се върхове; (б) е затворен и няма повтарящи се дъги; (в) или е незатворен или няма повтарящи се дъги.
Път (или контур) е елементарен, ако: (а) е дъга (или орпримка); (б) няма повтарящи се дъги; (в) няма повтарящи се върхове.
Не е вярно, че: (а) неелементарен контур може да се разложи поне на два елементарни контура; (б) неелементарен път може да се разложи на елементарен път и на един елементарен контур; (в) ако път от v до w и път от w до v, то орграфът е контурен.
Орграф е силно свързан, ако: (а) двойка различни върхове v и w, за които път от v до w и път от w до v; (б) за двойка различни върхове v и w път от v до w и път от w до v; (в) за двойка различни върхове v и w път от v до w.
Орграф е силно k-свързан: (а) ако е силно свързан за k двойки върха; (б) съответният неориентиран граф е k-свързан; (в) ако за двойка различни върхове v и w поне kнезависими пътя от v до w.
За симетричния орграф D=(V,A)не е вярно, че: (а) ако (v,w)А, то и (w,v)А; (б) ако (v,w)А, то (w,v)А; (в)D е изоморфен на съответния неориентиран граф.
За ориентирано дърво Т с корен v0не е вярно, че: (а)Т е дърво в неориентиран смисъл и единствената верига между v0 и друг връх w е път от v0 до w; (б)Т е симетричен орграф; (в)+(vi)=1, viv0, +(v0)=0 и контур в Т.
Ако D е силно свързан, двата ориентирани дъгови разреза за произволна върхова факторизация {W,W'}: (а) може да са празни; (б) са с равна мощност; (в) прекъсват пътищата от W към W' и обратно.
Матрицата на съседствата (аij)за орграф D е квадратна и аij е броят на: (а) дъгите от vi до vj; (б) ребрата между vi и vj; (в) върховете, инцидентни с vi и vj.
За орграф D и неговата матрица на съседствата (аij)не е вярно, че: (а)D е симетричен аij аji; (б)D е антисиметричен аij+аji1; (в)D е пълен аij+аji1.
Матрицата на съседствата не се използва при: (а) преброяване на пътища със зададени условия; (б) задачата за лидера; (в) задачата на Ойлер за кьонигсбергските мостове.
Не е вярно, че: (а) матрицата на инцидентностите на ребрата е напълно унимодуларна графът е двуделен; (б) матрицата на инцидентностите на ребрата е напълно унимодуларна; (в) матрицата на инцидентностите на дъгите е напълно унимодуларна.
Не е вярно, че орграфът е генеалогично дърво, ако: (а)+(v)2, vV, броят на ребрата на всеки редуващ се цикъл е кратен на четири и контур; (б) индивид има най-много двама родители, единият е баща, а другият – майка и никой не може да бъде свой потомък; (в)+(v)=2, vV, броят на ребрата на всеки редуващ се цикъл е четен и контур.
Реброва факторизация е: (а) подмножество от ребра, от които е или верига или цикъл; (б) разделяне на множеството на ребрата на непресичащи се подмножества, от които е или верига или цикъл; (в) разделяне на множеството на ребрата на подмножества, от които е или елементарна верига или елементарен цикъл.
Уникурсален граф е този, в който: (а) реброва факторизация е верига или цикъл; (б) единствен контур; (в) реброва факторизация от една верига или един цикъл.
Ако G=(V,E) е свързан ойлеров граф, то: (а) всички върхове имат нечетна степен; (б)Е е цикъл, образуващ единствена минимална реброва факторизация, покриваща G; (в)Е е верига, образуваща единствена минимална реброва факторизация, покриваща G.
Ако G е свързан граф с 2п върха от нечетна степен, то минимална реброва факторизация се състои от: (а)п вериги, от които съединява два върха от нечетна степен; (б)п цикли, от които съединява два върха от нечетна степен; (в)п вериги, от които съединява два върха от четна степен.
Свързаният граф е уникурсален той има: (а) 0 или 2 върха от нечетна степен; (б) 2 върха от нечетна степен; (в) 0 или 2 върха от четна степен.
Ориентиран ойлеров граф е орграф, за който: (а) +(v)+ –(v)=0, v; (б) +(v)= –(v) за v; (в)(v) е четно за v.
В ориентиран ойлеров граф D=(V,A) множеството Ане представлява: (а) контур; (б) минимална дъгова факторизация; (в) максимален дъгов разрез.
Ориентиран свързан граф е уникурсален (а) той е или ориентиран ойлеров граф или такъв, че има само два върха, в които разликата между + и – е единица; (б) той е ориентиран ойлеров граф; (в) той е или ориентиран ойлеров граф или такъв, че има само два неравновесни върха.
Свързан граф G е ориентируем като силно свързан орграф D : (а)G е ойлеров; (б) ребро на G принадлежи на поне един цикъл; (в)D е симетричен.
Хамилтонови верига или цикъл на свързан граф е: (а) елементарна верига или цикъл през всички върхове на графа; (б) верига или цикъл през всички върхове на графа; (в) елементарна верига или цикъл в графа.
Не евярно, че: (а) двуделен граф с нечетен брой върхове не съдържа хамилтонов цикъл; (б) пълен граф не притежава хамилтонов цикъл; (в) граф, притежаващ хамилтонов цикъл, притежава хамилтонова верига.
Хамилтонов път във : (а) несвързан антисиметричен граф; (б) пълен контурен граф; (в) пълен антисиметричен граф.
Не евярно, че: (а) пълният антисиметричен граф D има точно един хамилтонов път D е безконтурен; (б) безконтурният граф D има точно един хамилтонов път D е тотален; (в) в пълен антисиметричен граф D има четен брой хамилтонови пътища.
Подмножество S на V е вътрешно устойчиво множество, ако: (а)S не съдържа два съседни върха; (б) връх от допълнението на S е съседен на негов връх; (в)S не съдържа два несъседни върха.
Не евярно, че за максимално вътрешно устойчиво множество (макс.Вътр.УМ) и за доминиращо множество (ДМ) имаме: (а) макс.вътр.УМ е ДМ; (б) мощността на макс.вътр.УМ мощността на минималното ДМ; (в) допълнението на макс.вътр.УМ е също макс.Вътр.УМ.
Хроматичното число на графа е: (а) най-малкият брой вътрешно устойчиви множества, на които може да се раздели V; (б) най-голямото k, при което графът е k-делен; (в) броят цветове, необходими за оцветяването на върховете така, че два съседни върха да са разноцветни.
Не евярно, че: (а) хроматичен клас на графа G е броят цветове, необходими за оцветяването в различни цветове на съседните ребра на G; (б) хроматичен клас на графа G съвпада с хроматично число на дуалния граф на G; (в) задачата за определяне на хроматичен клас се свежда до задачата за определяне на хроматично число.
Ако графът G е бихроматичен, то G: (а) не съдържа цикли с нечетна дължина; (б) е дърво; (в) не е 2-делен.
За вътрешно устойчиво множество (Вътр.УМ) на Gне е вярно, че: (а) броят върхове на най-голямото Вътр.УМ е числото на вътрешната устойчивост на G; (б) произведението на числото на вътрешната устойчивост и хроматичното число е най-много реда на G; (в) подмножество на Вътр.УМ, което не е Вътр. УМ.
Подмножество от върхове ТV е външно устойчиво множество на графа G=(V,E), ако: (а) за vT wT: (v&w)E; (б) vT : wT, (v&w)E; (в) за vT, wT: (v&w)E.
Не е вярно, че: (а) числото на външната устойчивост на графа G=(V,E) е минималната мощност измежду външно устойчивите множества (ВнУМ) на G; (б)V е ВнУМ; (в) подмножество на ВнУМ е също ВнУМ.
Не е вярно, че: (а) отдалеченост на връх v е максималният брой ребра в най-късата верига между v и друг връх; (б) център на G е върхът с минимална отдалеченост от друг връх, а радиус на G е отдалечеността на центъра в G; (в) диаметърът на G е максималният брой ребра в най-късата верига между два върха в G и диаметърът на G е равен на два пъти радиуса на G.
За дърво на най-късите разстояния Т относно v0е вярно, че: (а) единственият път от v0до wv0на Т е най-късият път от v0до w; (б) за хорда (v,w), v,wТ, разстоянието по Т от v0до w е най-малко разстоянието по Т от v0до v плюс дължината на (v,w); (в)Т е единственото ориентирано дърво с корен v0 с тези свойства.
За мрежа N(V,A) е вярно: (а) чист поток през v в N е разликата между сумата от потоците по влизащите дъги във v и сумата от потоците по излизащите дъги от v; (б) потокът е ограничен от потоците 1 и 2, ако големината на по aA е между големините на 1 и 2 по aA; (в) потоците 1 и 2 са съгласувани, ако произведението на тези потоци по aA е отрицателно число.