Тесты для самоконтроля по теме «Графы и их элементы»


ГБПОУ КК «АМТ»
Тесты для самоконтроля
по теме
«Графы и их элементы»
Автор: Беляева Татьяна Юрьевна
2016
Вариант № 1
Задание № 1. (выберите один вариант ответа) Степень вершины А равна …
862965144780005581651447800026289014478000247651447800026289014478000
5581653810000247653810000
А
Варианты ответов:
0 2) 2 3) 4 4) 3
Задание № 2. (выберите один вариант ответа) Граф, изображенный на рисунке
3124835400050031489654000500243459040005002434590400050024345904000500

является…
Варианты ответов:
простым 2) ориентированным 3) мультиграфом 4) псевдографомЗадание № 3. (выберите один вариант ответа) Матрицу смежности
2 1 1
1 0 1
1 1 0
имеет следующий граф…
Варианты ответов:
1) 2) 3) 4)
-8953515557500-38481015557500
948690685800013201658763000-3848107620004215765106680004587240971550045872408763000421576597155002882265876300028778208763000260604097155009486909715500

-2324102032000
10960104762500
Задание № 4. (выберите два варианта ответов) Точкой сочленения в графе является вершина…
26289014478000247651447800026289014478000 АВ
-38481011049000
5581653810000247653810000 ●
С Д
Варианты ответов:
Д 2) В 3) С 4) А
Задание № 5. (выберите один вариант ответа) Две вершины графа называются смежными, если…
Варианты ответов:
они являются вершинами одного ребра
они являются граничными вершинами петель
их степени равны
существует маршрут от одной вершины до другой
Задание № 6. (выберите варианты ответов согласно тексту задания) Расположите ориентированные деревья в порядке убывания количества листьев в них…
51263557810500Варианты ответов:
4411980116205004819659715500441198011620500187261569850051263551162050051263559715500-514359715500291465116205001) 2) 3) 4)
3372485457200012630152667000268224045720002958465361950033724853619500

295846514287500
Задание №7. (выберите один вариант ответа) Граф называется смешанным, если он содержит…
Варианты ответов:
петли и кратные ребра; 2) ребра и дуги
3) мосты и точки сочленения 3) вершины разных степеней
Задание № 8. (выберите несколько вариантов ответов) Разделимым является граф…
Варианты ответов:
1) 2) 3) 4)
3110865196850029273514795500-533401670050029210014795500-533401193800015392401289050018726151289050022536151384300015392401384300031121352921000311213529210003902075292100031108651968500526351529210004520565292100045205652921000 ●
311213510731500 ● ●

Вариант № 2
Задание № 1. (выберите варианты ответов согласно тексту задания) Перечислите вершины графа в порядке возрастания степени вершины.
26289014478000247651447800026289014478000 АВ
-38481011049000
247653810000
С Д
Варианты ответов:
А 2) В 3) С 4) Д
Задание № 2. (выберите один вариант ответа) Граф, содержащий петли и / или кратные рёбра, называется…
Варианты ответов:
простым 2) полным 3) мультиграфом 4) псевдографомЗадание № 3. (выберите один вариант ответа) Граф
412753492500
113919048895001072515488950033147048895003314704889500
имеет следующую матрицу смежности…
Варианты ответов:
2) 3) 4)
2 1 0
1 0 2
0 2 2
0 1 1
1 0 2
1 2 0
2 1 1
1 0 1
1 1 0
2 1 1
1 0 2
1 2 0


Задание № 4. (выберите один вариант ответа) Замкнутый маршрут, содержащий все вершины графа (по одному разу), называется …
Варианты ответов:
циклом 2) простым циклом 3) гамильтоновым циклом 4) эйлеровым циклом
Задание № 5. (выберите несколько вариантов ответов) Уровень вершины А равен 1 у ориентированного дерева…
52616107810500Варианты ответов:
А
45472358763000280606522098000454723511620500526161010668000526161010668000328676028575000287274022098000156781522098000-16573518478500215265184785001) А 2) А 3) А 4)
11963404572000
Задание № 6. (выберите два варианта ответов) Один центр имеет следующее дерево…
Варианты ответов:
443484012700031248359715500454723510668000484251097155004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)
15240151765002476515240000-31813513144500
21869409334500

Задание № 7. (выберите один вариант ответа) Граф, изображенный на рисунке
-3181351028700031051510287000-3238510287000-323851028700069151510287000-31813510287000● ● ●
● ●
является…
однородным 2) полным 3) биграфом 4) суграфом
Задание № 8. (выберите один вариант ответа) Количество мостов графа
247651447800026289014478000
-38481011049000
247653810000
равно…
Варианты ответов:
1) 1 2) 3 3) 0 4) 2

Вариант № 3
Задание № 1. (выберите один вариант ответа) Степень вершины А равна…
862965144780005581651447800026289014478000247651447800026289014478000А
5581653810000247653810000
Варианты ответов:
0 2) 2 3) 4 4) 3
Задание № 2. (выберите один вариант ответа) Граф, изображенный на рисунке

31248354000500243459040005002434590400050024345904000500
243459013335000
является…
Варианты ответов:
простым 2) ориентированным 3) мультиграфом 4) псевдографомЗадание № 3. (выберите один вариант ответа) Матрицу смежности
2 1 0
1 0 1
0 1 2
имеет следующий граф…
Варианты ответов:
19627859715500338137597155004296410971550051631853619500
1) 2) 3) 4)
1320165171450004254576200004254576200002929890666750032061156667500320611576200004501515666750045015156667500
1318260-381000
21526511620500168973516637000
Задание № 4. (выберите один вариант ответа) Граф называется пустым, если он не содержит…
Варианты ответов:
петель 2) вершин 3) кратных рёбер 4) ни одного ребра
Задание № 5. (выберите несколько вариантов ответов) Две концевые вершины имеет граф…
3472815154305005166360781050031248351543050048425107810500Варианты ответов:
262890857250016897351066800044062658509000-270510106680007239010668000615959652000484251097155004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)

262890609600013182602228850024345906096000
Задание № 6. (выберите один вариант ответа) Замкнутый маршрут, содержащий все рёбра графа (по одному разу), называется …
Варианты ответов:
циклом 2) простым циклом 3) гамильтоновым циклом 4) эйлеровым циклом
Задание № 7. (выберите варианты ответов согласно тексту задания) Установите соответствие между графом
3768090128270004034790128270003768090128270003396615128270003396615128270005715128270006057901282700028194012827000571512827000А) Б)
281940635000
3768090825500033966158255000396811582550003396615825500091440825500041529082550007200908445500В) Г)
4152901778000
и числом точек сочленения в нем.
Варианты ответов:
1) 0 2) 1 3) 2 4) 3
Задание № 8. (выберите два варианта ответов) Два центра имеет следующее дерево…
52616106159500Варианты ответов:
45472357048500165354010668000443865381000443484012700031248359715500484251097155004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)
15240151765002476515240000-31813513144500
1958340933450021869409334500


Вариант № 4
Задание № 1. (выберите варианты ответов согласно тексту задания) Перечислите вершины графа в порядке убывания степени вершины.
247651447800026289014478000 АВ
59817011049000-38481011049000
247653810000
С Д
Варианты ответов:
А 2) В 3) С 4) Д
Задание № 2. (выберите один вариант ответа) Граф, содержащий рёбра и дуги, называется…
Варианты ответов:
простым 2) полным 3) смешанным 4) ориентированным
Задание № 3. (выберите несколько вариантов ответов) Граф, изображенный на рисунке
32918404000500329184040005002434590400050024345904000500
243459013081000329184013081000

является…
Варианты ответов:
циклическим 2) плоским 3) разделимым 4) планарным
Задание № 4. (выберите один вариант ответа) Количество мостов графа
247651447800026289014478000
-38481011049000
247653810000
равно…
Варианты ответов:
1) 1 2) 3 3) 0 4) 2
Задание № 5. (выберите один вариант ответа) Циклом называется…
Варианты ответов:
1) замкнутый маршрут 2) замкнутый путь
3) замкнутая цепь 4) всякий маршрут
Задание № 6. (выберите один вариант ответа) Граф
41275317500033147011303000
11410954889500331470488950033147048895003314704889500
имеет следующую матрицу смежности…
Варианты ответов:
2) 3) 4)
2 1 1
1 0 2
1 2 0
2 2 2
2 0 2
2 2 0
2 2 2
2 0 1
2 1 0
2 1 2
1 0 1
2 1 0


Задание № 7. (выберите два варианта ответов) Два центра имеет следующее дерево…
5166360781050048425107810500Варианты ответов:
4377690876300043776909715500484251097155004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)

-419101270000-41910133350023107658953500-419103429000-3848101333500
1485908445500148590163830009791701428750023107651428750013201654762500 ●
11963404381500
Задание № 8. (выберите один вариант ответа) Высота ориентированного дерева

16344909715500244411511620500163449097155001634490971550012630159715500
622935234950083439013335002434590234950012630151397000
62293515875001485901587500
равна…
Варианты ответов:
4 2) 5 3) 3 4) 2

Вариант № 5
Задание № 1. (выберите один вариант ответа) Степень вершины А равна …
862965144780005581651447800026289014478000247651447800026289014478000
5581653810000247653810000 А
Варианты ответов:
0 2) 2 3) 4 4) 3
Задание № 2. (выберите два варианта ответов) Граф, изображенный на рисунке
3148965400050024345904000500243459040005002434590400050024345904000500
243459013335000
является…
Варианты ответов:
циклическим 2) разделимым 3) неоднородным 4) полным
Задание № 3. (выберите один вариант ответа) Матрицу смежности
0 1 1
1 0 2
1 2 0
имеет следующий граф…
Варианты ответов:
1) 2) 3) 4)
-8953515557500-38481015557500
948690781050013201658763000-3848107620004215765106680004587240971550045872408763000421576597155002882265876300028778208763000260604097155009486909715500

-2324102032000
10960104762500
Задание № 4. (выберите один вариант ответа) Точкой сочленения в графе является вершина…
26289014478000247651447800026289014478000 ВА
-38481011049000
247653810000
С Д
Варианты ответов:
В 2) А 3) С 4) Д
Задание № 5. (выберите один вариант ответа) Граф называется однородным степени r, если…
Варианты ответов:
он содержит r вершин;
он содержит r ребер
степени всех его вершин равны r
он содержит r вершин и r ребер
Задание № 6. (выберите несколько вариантов ответов) Неразделимым является граф…
Варианты ответов:
1) 2) 3) 4)
-520709144000390207529210003112770387350015392401193800029146591440003112770387350029337014795500-514351289050015392401289050018726151289050022536151384300015392401384300031121352921000526351529210004520565292100045205652921000 ●
452056516383000311213510731500 ● ● ●

Задание № 7. (выберите варианты ответов согласно тексту задания) Расположите ориентированные деревья в порядке возрастания количества листьев в них…
51263557810500Варианты ответов:
44119809715500481965135255002914651162050018726156985004411980971550051263551162050051263559715500-5143597155001) 2) 3) 4)
1263015266700026822404572000295846536195003372485361950015392404572000

Задание № 8. (выберите один вариант ответа) Два ребра называются кратными, если они…
Варианты ответов:
имеют общую граничную вершину 2) инцидентны одной вершине
3) не пересекаются 4) инцидентны одной паре вершин

Вариант № 6
Задание № 1. (выберите несколько вариантов ответов) Степень, равную трем, имеют следующие вершины…
24765144780005581651447800026289014478000247651447800026289014478000 АВ
-38481011049000
247653810000
С Д
Варианты ответов:
А 2) В 3) С 4) Д
Задание № 2. (выберите один вариант ответа) Граф, содержащий кратные рёбра, называется…
Варианты ответов:
простым 2) полным 3) мультиграфом 4) псевдографомЗадание № 3. (выберите один вариант ответа) Граф
412756667500
1141095488950033147048895003314704889500
имеет следующую матрицу смежности…
Варианты ответов:
1) 2) 3) 4)
2 1 0
1 0 2
0 2 2
0 1 1
1 0 2
1 2 0
2 1 1
1 0 1
1 1 0
2 1 1
1 0 2
1 2 0


Задание № 4. (выберите один вариант ответа) Замкнутый маршрут, который проходит через различные вершины графа, называется …
Варианты ответов:
гамильтоновым циклом 2) циклом 3) простым циклом 4) эйлеровым циклом
Задание № 5. (выберите варианты ответов согласно тексту задания) Расположите ориентированные деревья в порядке убывания их высоты
52616107810500Варианты ответов:
А
56807101066800045472358763000280606522098000526161010668000328676028575000287274022098000156781522098000-16573518478500215265184785001) А 2) А 3) А 4)
2596515457200075819045720004057654572000190119045720001901190457200011963404572000
Задание № 6. (выберите два варианта ответов) Два центра имеет следующее дерево…
Варианты ответов:
443484012700031248359715500454723510668000484251097155004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)
15240151765002476515240000-31813513144500
21869409271000
Задание № 7. (выберите один вариант ответа) Граф, изображенный на рисунке
31051510287000-31813510287000-3181351028700031051510287000-3238510287000-323851028700069151510287000-31813510287000● ● ●
-3238511049000 ● ●
является…
однородным 2) полным 3) планарным 4) плоским
Задание № 8. (выберите один вариант ответа) Количество точек сочленения графа
247651447800026289014478000
-38481011049000
247653810000
равно…
Варианты ответов:
1) 1 2) 3 3) 0 4) 2

Вариант № 7
Задание № 1. (выберите один вариант ответа) Сумма степеней всех вершин графа
558165144780002628901447800026289014478000
43434038100005581653810000247653810000
равна…
Варианты ответов:
10 2) 12 3) 11 4) 13
Задание № 2. (выберите один вариант ответа) Граф, изображенный на рисунке
2434590400050031248354000500243459040005002434590400050024345904000500
243459013335000
является…
Варианты ответов:
простым 2) ориентированным 3) неориентированным 4) смешанным
Задание № 3. (выберите один вариант ответа) Граф называется пустым, если он не содержит…
Варианты ответов:
вершин 2) петель 3) рёбер 4) кратных рёбер
Задание № 4. (выберите один вариант ответа) Матрицу смежности
2 1 0
1 2 1
0 1 0
имеет следующий граф…
Варианты ответов:
19627859715500338137597155004296410971550051631853619500
1) 2) 3) 4)
1320165171450004254576200004254576200002929890666750032061156667500320611576200004501515666750045015156667500
1318260-381000
21526511620500168973516637000
Задание № 5. (выберите один вариант ответа) Замкнутый маршрут, все ребра которого различны, называется …
Варианты ответов:
простым циклом 2) эйлеровым циклом 3) гамильтоновым циклом 4) циклом
Задание № 6. (выберите варианты ответов согласно тексту задания) Установите соответствие между графом и его свойством…
1320165508000165354010668000131826078105001962785106680004406265857250049022085725002901315781050044062651066800029013158509000271081585090009144010668000-31813510668000-2705101066800061595965200048425109715500132016510668000А) Б) В) Г)
132651511430000
196278514732000196278514732000-27051061595002152656159500-2705101181100013182602228850024345906096000
44348404762500
Варианты ответов:
однородный 2) ациклический 3) планарный 4) несвязный
Задание № 7. (выберите несколько вариантов ответов) Два моста имеет граф…
Варианты ответов:
37680901282700037680901282700033966151282700033966151282700057151282700060579012827000281940128270005715128270001) 2)
281940635000
41529082550003768090825500033966158255000914408255000415290825500072009084455003) 4)
4152901778000
Задание № 8. (выберите два варианта ответов) Один центр имеет следующее дерево…
Варианты ответов:
34747201593850045472357048500165354010668000443865381000443484012700031248359715500484251097155004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)
15240151765002476515240000-31813513144500
21869409334500
13182604762500

Вариант № 8
Задание № 1. (выберите варианты ответов согласно тексту задания) Перечислите вершины графа в порядке возрастания степени вершины.
247651447800026289014478000 АВ
59817011049000-38481011049000
247653810000
С Д
Варианты ответов:
А 2) В 3) С 4) Д
Задание № 2. (выберите один вариант ответа) Граф, содержащий дуги, называется…
Варианты ответов:
простым 2) полным 3) смешанным 4) ориентированным
Задание № 3. (выберите два варианта ответов) Граф, изображенный на рисунке
32918404000500329184040005002434590400050024345904000500
243459013081000329184013081000

является…
Варианты ответов:
циклическим 2) плоским 3) разделимым 4) однородным
Задание № 4. (выберите один вариант ответа) Граф
41275317500033147011303000
331470488950033147048895003314704889500
имеет следующую матрицу смежности…
Варианты ответов:
1) 2) 3) 4)
2 2 0
2 0 2
0 2 2
2 2 2
2 0 0
2 0 0
0 2 2
2 0 0
2 0 2
2 0 2
0 0 2
2 2 0


Задание № 5. (выберите один вариант ответа) Контуром называется…
Варианты ответов:
всякий маршрут 2) замкнутый маршрут
3) замкнутый путь 4) замкнутая цепь
Задание № 6. (выберите один вариант ответа) Количество точек сочленения графа
247651447800026289014478000
1524021336000-38481011049000
равно…
Варианты ответов:
1) 3 2) 2 3) 1 4) 0
Задание № 7. (выберите несколько вариантов ответов) Два центра имеет следующее дерево…
48425107810500Варианты ответов:
4644390876300052730401066800052616109715500437769087630004842510971550031248359715500271081597155001320165106680001) 2) 3) 4)

190119014605003867151460500-419101270000-41910133350023107658953500-419103429000-3848101333500
148590163830009791701428750023107651428750013201654762500
11963404381500
Задание № 8. (выберите один вариант ответа) Высота ориентированного дерева

16344909715500163449097155001634490971550012630159715500
6229352349500834390133350012630151397000
62293515875001485901587500
равна…
Варианты ответов:
5 2) 4 3) 3 4) 2

Ответы:
№ задания В1 В2 В3 В4 В5 В6 В7 В8
1. 3 2413 4 3412 2 124 2 2143
2. 3 4 2 3 14 3 4 4
3. 2 4 2 134 4 2 3 13
4. 14 3 4 2 1 3 4 4
5. 1 134 124 3 3 1432 1 3
6. 3421 14 4 3 124 23 А3Б1
В2Г4 2
7. 2 3 А3Б1
В4С2 13 1324 3 134 134
8. 234 2 14 1 4 4 34 3

Приложенные файлы

  • docx file23
    Размер файла: 576 kB Загрузок: 19