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

(б) ако  е допустим поток с големина k от vW до w=V\W, за про­­­из­волна факторизация {W,}на V, то ; (в) N(V,A) има капацитет, ако са дадени две целочислени функции  и  върху А: 0(а)(а), aA.

Ако  поне един допустим поток  от vW до w=V\W за про­из­волна факторизация {W,} на V, то , където и са съответно: (а) горната и долната граница на капацитета на ; (б) максималната и минималната гра­ни­ца на големините на допустимите потоци; (в) минималната и максималната граница на голе­ми­ни­те на допустимите по­то­ци.

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

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

Сдвояване в граф без примки G=(V,E) е множество: (а) М  Е, ако в М  съседни ребра; (б) М  Е, ако в М  2 ребра са съседни; (в) М  V, ако в М  съседни върхове.

Теоремата на Кьониг-Хол за сватбите гласи: (а) В пълен двуделен граф G(V₁,V₂;Г)  пълно сдвояване на V₁ с V₂  ,SV; (б) В двуделен граф G(V₁,V₂;Г)  пълно сдвояване на V₁ с V₂  ,SV; (в) В двуделен граф G(V₁,V₂;Г)  пълно сдвояване на V₁ с V₂  , SV.

За прост двуделен граф G(V₁,V₂;Г) с дефицит не е вярно, че: (а) min брой вър­хо­ве на опората е равен на max брой дъги на сдвояването; (б) числото на външната устойчивост на G е (G)=; (в) max брой дъги на сдвояване е .

В унгарския алгоритъм за построяване на максимално сдвояване се използва еквивалентността на следните твърдения: (а) сдвояването М е максимално в простия двуделен граф G(V₁,V₂;Г)   път от М⁺ в М ^– в графа (М,); (б) сдвояването М е максимално в графа G   сдвояването с по-голяма мощност в G; (в) сдвояването М е максимално в простия двуделен граф G(V₁,V₂;Г)   редуващи се вериги от силни и слаби дъги, съединяващи два различни ненаситени върха.

Граф G=(V,Е) има 1-фактор  (а) броят на нечетните компоненти на подграфа G' [V \ S], SV, е ра­вен на S (мощността на S); (б) броят на четните компоненти на подграфа G' [V \ S], SV, е поне S; (в) броят на нечетните компоненти на подграфа G' [V \ S], SV, е най-много S.

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

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

Ако G е п-граф, който не съдържа път с дължина k, то размерът на G е най-много (k–1)п / 2 и екс­тре­мал­ните графи на това неравенство са: (а) графи на Мур; (б) свързани графи с всички блокове свър­за­ни k-графи; (в) графи с компоненти пълни k-графи.

Теоремата на Туран за пълните графи гласи: (а) Максималният брой ребра в п-граф, несъдържащ пъ­лен r-граф е равен на броят на ребрата на пълен (r–1)-делен п-граф; (б) Графът на Туран Т_r–1(п) има върха в k-тия си клас; (в) Броят на ребра на пълен (r–1)-делен п-граф е равен на размера на гра­фа на Туран Т_r–1(п).

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

160. 
     Формулата на Ойлер за свързан равнинен граф с n върха, m ребра и f области е: (а) n – m + f = 2; (б) m – n + f = 2; (в) n + m – f = 2.
     
161. 
     Не е вярно, че: (а) графите на Понтрягин-Куратовски са равнинни; (б) графът на Понтрягин-Кура­тов­ски от I тип е пълният граф от ред 5; (в) графът на Понтрягин-Кура­тов­ски от II тип е пълният дву­де­лен граф с 3 върха в единия клас и 3 върха в другия клас.
     
162. 
     Кое от следните НДУ за равнинност на граф G не е вярно: (а) G не съдържа подграф, изоморфен с точ­ност до връх от степен 2 на един от графите K₅ и K_3,3; (б) G съдържа база от цикли и един до­пъл­ни­телен цикъл, такъв че тази съвкупност от цикли да съдържа точно 2 пъти  ребро на G; (в) G да има спрегнат граф.
     
163. 
     Дуален граф на G е граф , получен от G чрез еднозначно съпоставяне: (а) на  област на G – връх на , като се запазва релацията съседство; (б) на  ребро на G – връх на , като се запазва ре­ла­ци­я­та съседство; (в) на  връх на G – връх на , като се запазва релацията съседство.
     
164. 
     Многостенен граф е правилен, ако: (а) е хомогенен и дуалният му граф е също хомогенен; (б)  не­гов връх има една и съща степен; (в) може да се отъждестви с изпъкнал многостен в евклидовото про­странство.
     
165. 
     Не е вярно, че: (а) единствените нетривиални правилни многостенни графи са 5; (б) тетраедърът е ду­ален сам на себе си; (в) кубът е дуален на додекаедъра, а октаедърът – на икосаедъра.
     
166. 
     k-оцветяване на върховете на граф G=(V,E) наричаме: (а) функция с: V{1,2,…,k}, такава че  мно­жест­во с^–1(j) е вътрешно устойчиво; (б) функция с: V{1,2,…,k}, такава че всички мно­жест­ва с^–1(j) са раз­лич­ни; (в) биективна функция с: V{1,2,…,k}.
     
167. 
     Ако за всички породени подграфи Н на G, тогава за хроматичното число на G имаме: (а) ; (б) ; (в) .
     
168. 
     Ако графът G съдържа пълен подграф K, без който G се разпада на компоненти Н₁, Н₂,…, то за хро­ма­тичните числа на G и на породените подграфи G_i =K+H_i, i=1,2,… имаме: (а) ; (б) ; (в) .
     
169. 
     Ако G е свързан граф с максимална степен _max и G не е нито пълен граф, нито цикъл с нечетна дъл­жи­на, то­га­ва според теоремата на Брукс: (а) ; (б) ; (в) .
     
170. 
     Ако за два съседни върха a и b на граф G са получени от G два графа – G' чрез свързване на a и b и G'' чрез отъждествяване на a и b, тогава: (а) хроматичното число на G е по-голямото между хро­ма­тич­ните числа на G' и на G''; (б) броят на оцветяванията на G е сумата от оцветяванията на G' и на G''; (в) съответствието между оцветяванията на G, при които a и b са оцветени еднакво и оцветя­ва­ни­ята на G' е взаимно еднозначно.
     
171. 
     Според теоремата на Визинг хроматичният клас на граф G е: (а) или _max(G) или _max(G)+1; (б) най-много _max(G); (в) най-малко _max(G)+1.
     
172. 
     Всеки равнинен граф е: (а) 5-оцветим; (б) 4-оцветим; (в) 3-оцветим.
     
173. 
     Броят на цветовете, необходими за оцветяване на граф върху ориентируема повърхнина от род е най-много: (а); (б); (в) .
     

Каталог: manev -> Graphs -> tests
tests -> Тест №1 по Теория на графите
tests -> Тест по Теория на графите
tests -> Тест №2 по Теория на графите