АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Тестілік тапсырма

1 нұсқа

1. K₃ графтың сыбайлас матрицасын көрсет:

A) B) C) D) E)

2. P₃ графқа толықтауыш болатын графтың сыбайлас матрицасы...:

A) B) C) D) E)

3. 6 төбе және 10 қабырғадан тұратын графтың төбелер дәрежелерінің қосындысы тең:

A)10 B)16 C)6 D)20 E)12

4. 9 төбеден тұратын граф k дәрежелі біртекті болу үшін k-ның мәні қандай санға тең болу керек?

A)1 B)3 C)4 D)5 E)7

5. Егер G – байланыссыз граф болса, онда:

A) байланысcыз B) байланысты Г) байланысты

D) байланысты та, байланыссыз да болуы мүмкін

E) байланысты болады, егер G нуль-граф болса ғана

6. 6 төбеден тұратын байланыссыз графтың қабырғаларының ең үлкен саны тең:

A) 4 B)6 C)8 D)10 E)12

7. Келесі тізбектердің қайсысы байланыссыз графтың төбелер дәрежелерінің тізбегін анықтайды.

A)3,3,3,3 B) 2,2,2,2 C)0,2,2,2 D)1,3,2,2 E)2,2,3,3

9. Дәрежесі 3-ке, ал қабырғалар саны 12-ге тең болатың біртекті графтың төбелер саны тең:

A)6 B)8 C)10 D)12 E)14

10. Келесі қабырғалар тізбектерінің қайсысы 5 төбелі байланысты графты анықтайды:

A)(1,2),(1,3),(1,4) B)(1,2),(1,3),(2,5) C)(1,2),(1,3),(1,4),(1,5)

D)(1,2),(3,4),(4,5) E)(1,2),(1,3),(1,4),(2,3)

11. Төбелер дәрежелерінің жиынтығы (1,2,2,3) тең болғанда қабырғалар саны тең:

A)2 B)3 C)4 D)5 E)6

12. Келесі графтардың қайсысы кубтық болып табылады:

A) тізбе B)цикл C)K₅ D)кубтың графы E)октаэдрдың графы

13. Келесі графтардың қайсысы 4 дәрежелі біртекті граф болып табылады:

A) K₄ B)Р₄ C)C₄ D)К₆ E) октаэдрдың графы

14. 7 төбеден тұратын «орманның» қабырғаларының саны тең:

A)2 B)4 C)6 D)8 E)10

15. Келесі қабырғалар тізбегімен берілген 5 төбелі граф «ағаш» болып табылады:

A)(1,2),(1,3),(3,2),(2,4),(2,5) B)(1,2),(2,3),(4,5) C)(1,2),(1,3),(1,4),(1,5)

D)(1,2),(1,3),(3,2),(4,5) E)(1,2),(2,3),(3,4),(4,1)

16. р- төбелі граф «ағаш» болып табылады, егер:

A) оның ішінде циклдары болмаса B)байланысты болса C) қабырғалар саны q=p-1болса

D) қабырғалар саны ең кіші болатын байланысты граф

E) қабырғалар саны ең үлкен болатын байланысты граф

17. Келесі графтардың қайсысы екібөлікті болып табылады:

A)К₃ B)С₃ C)К₄ D)С₄ E)К₅

18. Келесі графтардың қайсысы екібөлікті болып табылады:

A)кубтың B)октаэдрдың C)Петерсен граф D) «колесо» E) К₄

19. K_n,m графты эйлер графы деп атаймыз, егер:

A)n=m=2k+1 B) n=m=2k C) n=2k, m=2l+1

D)n=2k, m=2l E)n=2k+1, m=2l

20. Үшбұрыштары жоқ р- төбелі графтың қабырғаларының ең үлкен саны тең:

A) B) C) D) E)

21. Егер бағытталған графтың доғаларының саны 10-ға тең болса және m, n –төбелерінің сәйкесінше кіру және шығу жарты дәрежелерінің қосындылары болса, онда:

A) n=m=5 B) n=m=10 C) n=m=15 D) m=n-1 E) n=m-1

22. (1,2),(1,3),(2,3) доғаларымен берілген бағытталған графтың төбелерінің сыбайлас матрицасы:

A) B) C) D) E)

23. (1,2),(1,6),(2,5),(3,4),(4,5) қабырғалары бар 6- төбелі графтың 3 және 6 төбелерінің ара қашықтығы тең...

24. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың диаметрі тең...

25. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1)) қабырғалары бар 6- төбелі графтың радиусы тең...

26. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың төбелерінің келесі жиындарының қайсысы тәуелсіз болады:

A) {1,2,3} B) {1,2,4} C) {3,5,1} D) {3,5,2} E) {3,5}

27. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5 төбелі графтың клика болып табылатын жиынды көрсет:

A) {1,2,3} B) {1,2,4} C) {2,3,5} D) {2,3,4} E) {1,2,5}

28. Бағытталған графты күшті байланысты болады дейміз, сонда тек сонда, егер:

A) оның табаны – толық граф болса

B) оның табаны – эйлер граф болса

C) остовты бағыт табылса

D) остовты циклі бар бағыт табылса

E) оның табаны – гамильтон граф болса

29. К_2n толық графтың диаметрі тең...

30. Куб графтың диаметрі тең...

2 нұсқа

1. K_1,2 графтың сыбайлас матрицасы келесі түрінде жазылады:

A) B) C) D) E)

2. K₃ графқа толықтауыш болатын графтың сыбайлас матрицасын көрсет:

A) B) C) D) E)

3. 5 төбеден және 6 қабырғадан тұратын графтын төбелер дәрежелерінің қосындысы:

A)5 B)10 C)12 D)15 E)16

4. Төбелер дәрежелерінің тізбектерінің қайсысы 5 төбелі графты анықтайды:

A)1,2,3,4,5 B)0,2,2,4,5 C)0,3,3,4,5

D)1,2,2,3,4 E)0,2,3,3,3

5. Егер G байланысты граф болса, онда:

A) - байланыссыз B) - байланысты C) - байланыссыз

D) - байланысты және байланыссыз да болуы мүмкін

E) -байланыссыз, егер G- толық граф болса ғана

6. Толық графтың сыбайлас матрицасын көрсетіңіз:

A) B) C) D) E)

7. K_n графтың қабырғалар саны тең:

A)n B)n-1 C)n(n-1) D) E)n(n+1)

8. Келесі тізбектердің қайсысы байланысты графтың төбелер дәрежелерін анықтайды:

A)0,2,2,2 B) 1,1,1,1 C)0,1,1,2 D)2,2,3,3 E)0,0,1,1

9. Төбелер дәрежелерінің жиынтығы (2,2,2,3,3) тең болатындай графтың қабырғалар саның есептеңіз:

A)3 B)4 C)5 D)6 E)7

10. Келесі граф екі дәрежелі біртекті граф болып табылады:

A) кубтың графы B) тетраэдрдың графы C)тізбе

D) цикл E) кез келген толық граф

11. 3 байланысты компоненттерден тұратын 12 төбелі «орманның» қабырғалар саны тең:

A)3 B)6 C)9 D)12 E)15

12. (1,2)(1,4)(2,3)(3,4) қабырғалар тізбегімен берілген граф қандай болады?

A) регуляр B)ағаш C)байланысты емес

D)толық E)орман

13. Кез келген ағаш үшін қандай тұжырым дұрыс болады:

A) толық болады B)нуль-граф болады C)екі бөлікті болады

D)байланысты емес болады E)біртекті граф болады

14. Келесі графтарының қайсысы K_3,4 графтың ішкі графы болып табылады?

A)K₃ B)C₃ C)K_1,2 D)K₄ E)K₇

15. Келесі графтардың қайсысы ағаш болып табылады:

A)кубтың графы B)октаэдр графы C)Петерсен графы

D) «колесo» E) K_1,n

16. матрицасы келесі қандай графтың сыбайлас матрицасы болып табылады:

A)K₃ B) C)K_1,2 D)P₃ E)C₃

17. Эйлер графтың сыбайлас матрицасын көрсет:

A) B) C) D) E)

18. Жарты эйлер графты тап:

A)кубтың графы B)октаэдр графы C)Петерсен графы

D) n=2k төбелі колесо E)K_2,3

19. K_1,2 графқа толықтауыш болатын графтың сыбайлас матрицасы келесі түрінде жазылады:

A) B) C) D) E)

20. Келесі доғалар тізбектерінің қайсысы 5- төбелі әлсіз байланысты графты анықтайды:

A) (1,2),(2,3),(3,4),(4,1) B) (1,2),(2,3),(3,4)

C) (1,2),(2,3),(3,1),(4,5) D) (1,2),(2,3),(3,4),(5,1)

E) (1,2),(2,3),(4,5)

21. (1,2),(1,3),(1,4),(3,2),(3,4),(4,2) доғаларымен берілген турнирдың остовты жолы келесі төбелерінің тізбегімен анықталады:

A) 1,2,3,4 B) 1,2,4,3 C) 1,3,2,4 D) 1,3,4,2

E) 1,4,3,2

22. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың 2 және 3 төбелерінің ара қашықтығы тең равно...

23. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың диаметрі тең...

24. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың 3- ші төбесінің эксцентриситеті тең...

25. (1,2),(2,3),(3,4),(4,5) қабырғалары бар 5- төбелік графтың орталық төбесі...

26.( 1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың төбелерінің келесі жиындарының қайсысы тәуелсіз болады:

A) {1,2,3} B) {2,3,4} C) {2,3,5} D) {3,4,5} E) {3,5,6}

27. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6 төбелі графтың келесі жиыны клика болып табылады:

A) {1,2,3} B) {1,2,4} C) {2,3,5} D) {2,3,4} E) {1,2}

28. Бағытталған графты күшті байланысты болады дейміз, сонда тек сонда, егер:

A) оның табаны – толық граф болса

B) оның табаны – эйлер граф болса

C) остовты бағыт табылса

D) остовты циклі бар бағыт табылса

E) оның табаны – гамильтон граф болса

29. р-төбелі байланыссыз графтың қабырғаларының ең үлкен саны тең:

A) B) C) +1

D) E)

30. Октаэдрдр графтың диаметрі тең...

3 нұсқа

1. C₃ графтың сыбайлас матрицасын көрсетіңіздер:

A) B) C) D) E)

2. матрицасы қандай графтың сыбайлас матрицасы болып табылады

A) бос графтың B)толық графтың C) толық графқа толықтауыш

D) тізбе E) циклге толықтауыш

3. 6 қабырғалы 4 дәрежелі біртекті болатын графтың қабырғалар саны тең:

A)6 B)8 C)10 D)12 E)14

4. 4 төбелі графтың төбелер тізбегін көрсет:

A)0,1,2,3 B) 1,2,3,4 C)0,1,1,3 D)2,2,3,3 E)0,2,2,3

5. 6 төбелі байланысты болатын графтың қабырғаларының ең кіші саны:

A) 1 B)2 C)3 D)4 E)5

6. Толық графтың сыбайлас матрицасын көрсет:

A) B) C) D) E)

7. K_n графтың қабырғалар саны тең:

A)n B)n-1 C)n(n-1) D) E)n(n+1)

8. Келесі тізбектердің қайсысы байланысты графтың төбелер дәрежелерін анықтайды:

A)0,2,2,2 B) 1,1,1,1 C)0,1,1,2 D)2,2,3,3 E)0,0,1,1

9. 4 дәрежелі біртекті 12 қабырғадан тұратын графтың төбелер саны тең:

A)4 B)6 C)8 D)10 E)12

10. Келесі графтардың қайсысы 4 дәрежелі біртекті граф болып табылады:

A) K₄ B)Р₄ C)C₄ D)К₆ E) октаэдрдың графы

11. 3 байланысты компоненттерден тұратын 10 төбелі байланыссыз графтың қабырғаларының ең кіші саны тең:

A)6 B)7 C)8 D)9 E)10

12. Келесі тізбектерінің қайсысы4 төбелі екібөлікті графтың қабырғалар тізбегін анықтайды

A)(1,2),(2,3),(3,1),(1,4) B)(1,2),(1,3),(1,4) C)(1,2),(2,3),(3,4),(4,1)

D)(1,2),(2,3),(3,1) E)(1,2),(2,3),(3,1),(2,4)

13. Келесі графтардың қайсысы ағаш болып табылады:

A)К_n (n ) B)С_n C) К_n,m

D)К_n,m егер n=1 немесе m=1 E) біртекті граф

14. (1,2),(1,4),(2,3),(3,4) қабырғалар тізбегімен берілген граф қалай аталады:

A) ағаш B)толық С) регуляр D)екібөлікті E)байланысты емес

15. Граф эйлер болып табылады, егер:

A) байланысты болса

B) барлық төбелерінің дәрежелері жұп болса

C) Әрбір төбесі бір рет қана кіретін циклы болса

D) байланысты болса, және барлық төбелерінің дәрежелері жұп болса

E) төбелер саны тақ болатындай толық граф болса

16. «Ағаштың» сыбайлас матрицасы келесі түрінде жазылады:

A) B) C) D) E)

17. (1,2),(1,3),(2,3),(3,4),(3,5),(4,5),(1,5) қабырғалар тізбегімен берілген графты қалай атаймыз?

A) ағаш B) толық C) екібөлікті D) регуляр E)жарты эйлерлік

18. Эйлер графты көрсет:

A)К_n (n=2k) B)К_n (n=2k+1) C)К_n,m,n және m тақ сандар

D)К_n,m где n=2k+1, m=2l E)ағаштың толықтауыш графы

19. Октаэдрдың графы:

A) толық B) эйлерлік C) жартыэйлер

D)екі болікті E)нуль-граф

20. Келесі доғалар тізбектерінің қайсысы 5- төбелі күшті байланысты графты анықтайды:

A) (1,2),(1,3),(1,4),(1,5),(5,2)

B) (1,2),(1,3),(1,4),(1,5)

C) (1,2),(1,3),(4,1),(5,1)

D) (1,2),(1,4),(2,3),(3,5),(4,2),(5,1)

E) (1,2),(1,3),(4,1),(5,1),(5,2)

21. (1,2),(1,6),(2,5),(3,4),(4,5) қабырғалары бар 6- төбелі графтың 3 және 6 төбелерінің ара қашықтығы тең...

22. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың радиусы тең...

23. 1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың 4- ші төбесінің эксцентриситеті тең...

24. Егер байланысты графтың диаметрі 4-ке тең болса, онда радиусы тең бола алады:

A) 1 B) 2 C) 5 D) 6 E) 7

25. K_n,m толық екі бөлікті графтың радиусы тең...

26. 8- төбелік G кубтық графтың b₀(G) төбелік тәуелсіздігінің саны келесі шартты қанағаттандырады:

A) b₀(G) = 1 B) b₀(G) = 2 C) b₀(G) ³ 2

D) b₀(G) = 3 E) b₀(G) ³ 3

27. Келесі графтардың қайсысының төбелік тәуелсіздігінің саны 1-ге тең болады:

A) K_n B) C_n C) P_n D) E)

28. р – төбелі гамильтон болмайтын графтың қабырғаларының ең үлкен саны тең:

A) B) C) +1

D) E)

29. Бағытталған графты күшті біржақты байланысты болады дейміз, сонда тек сонда, егер:

A) оның табаны – толық граф болса

B) оның табаны – эйлер граф болса

C) остовты бағыт табылса

D) остовты циклі бар бағыт табылса

E) оның табаны – гамильтон граф болса

30. K_n,m толық екі бөлікті графтың радиусы тең...

4 нұсқа

1. C₃ графтың сыбайлас матрицасын көрсет:

A) B) C) D) E)

2. матрицасы келесі графтың сыбайлас матрицасы болып табылады

A) бос графтың B)толық графтың C) толық графқа толықтауыш

D) тізбе E) циклге толықтауыш

3. 6 қабырғалы 4 дәрежелі біртекті болатын графтың қабырғалар саны тең:

A)6 B)8 C)10 D)12 E)14

4. 4 төбелі графтың төбелер тізбегін көрсет:

A)0,1,2,3 B) 1,2,3,4 C)0,1,1,3 D)2,2,3,3 E)0,2,2,3

5. 6 төбелі байланысты болатын графтың қабырғаларының ең кіші саны:

A) 1 B)2 C)3 D)4 E)5

6. K_n графтың қабырғалар саны тең:

A)n B)n-1 C)n(n-1) D) E)n(n+1)

7. Келесі тізбектерінің қайсысы байланысты графтың төбе дәрежелерінің тізбегін анықтайды:

A)0,2,2,2 B) 1,1,1,1 C)0,1,1,2 D)2,2,3,3 E)0,0,1,1

8. 4 дәрежелі біртекті 12 қабырғасы бар графтың төбелер саны тең:

A)4 B)6 C)8 D)10 E)12

9. Келесі тізбектерінің қайсысы 4 төбелі байланысты графтың қабырғалар тізбегін анықтайды:

A)(1,2),(2,3),(3,4) B)(1,2),(2,3),(3,4),(4,1) C)(1,2),(2,3),(3,1)

D)(1,2),(2,3),(3,1),(4,1) E)(1,2),(2,3),(3,4),(2,4)

10. Төбелердің дәрежелері (2,2,2,3,3) тізбегімен берілген графтың қабырғалар саны тең:

A)3 B)4 C)5 D)6 E)7

11. Келесі графтардың қайсысы екі дәрежелі біртекті болады:

A) кубтың графы B) тетраэдрдың графы C)тізбе

D) цикл E) кез келген толық граф

12. 3 байланысты компоненттерден тұратын 12 төбелі «орманның» қабырғалар саны тең:

A)3 B)6 C)9 D)12 E)15

13. (1,2)(1,4)(2,3)(3,4) қабырғалар тізбегімен берілген графтың түрін анықта:

A) регуляр B)ағаш C)байланысты емес

D) толық E)орман

14. Кез келген ағаш үшін қандай тұжырым дұрыс болады:

A) толық болады B)нуль-граф болады C)екі бөлікті болады

D) байланысты емес болады E)біртекті граф болады

15. Келесі графтардың қайсысы K_3,4 графтың ішкі графы болып табылады?

A)K₃ B)C₃ C)K_1,2 D)K₄ E)K₇

16. Келесі графтардың қайсысы ағаш болып табылады:

A)кубтың графы B)октаэдр графы C)Петерсен графы

D) «колесo» E) K_1,n

17. матрицасы қандай графтың сыбайлас матрицасы болып табылады:

A)K₃ B) C)K_1,2 D)P₃ E)C₃

18. (1,2),(1,3),(2,3),(3,4),(3,5),(4,5) қабырғалар тізбегімен берілген графты қалай атаймыз?

A) ағаш B)толық C) екі бөлікті D) регуляр E)эйлерлік

19. (1,2)(2,3)(4,5)(5,6)(4,6) қабырғалар тізбегімен берілген графты қалай атаймыз?

A) орман B)толық C)байланысты емес D) екі бөлікті E)гамильтон

20. Бағытталған графты күшті байланысты деп атаймыз, егер:

A) оның табаны(негізі) байланысты граф болса

B) екі төбесінен кем дегенде біреуінен екіншісіне жетуге болатын төбелер жұбы табылса

C) өзара жетуге болатын төбелер жұбы табылса

D) кез кеген төбелер жұбы өзара жетерлік болса

E) кез келген екі төбелерінің біреуі екіншісінен жетерлік болса

21. (1,2),(1,6),(2,5),(3,4),(4,5) қабырғалары бар 6- төбелі графтың 3 және 6 төбелерінің ара қашықтығы тең...

22. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың диаметрі тең...

23. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1)) қабырғалары бар 6- төбелі графтың радиусы тең...

24. (1,2),(2,3),(3,4),(4,5),(5,6) қабырғалары бар 6- төбелік графтың орталық төбесі...

25. К_2n толық графтың диаметрі тең...

26. K_n,m толық екі бөлікті графтың радиусы тең...

27. Петерсен графтың диаметрі тең...

28. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың төбелерінің келесі жиындарының қайсысы тәуелсіз болады:

A) {1,2,3} B) {1,2,4} C) {3,5,1} D) {3,5,2} E) {3,5}

29. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5 төбелі графтың клика болып табылатын жиынды көрсет:

A) {1,2,3} B) {1,2,4} C) {2,3,5} D) {2,3,4} E) {1,2,5}

30. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың қабырғаларының тәуелсіз жиының көрсет:

A) {(1,5),(2,5)} B) {(1,5),(2,3)} C) {(2,3),(3,4)}

D) {(2,3),(4,5),(1,5)} E) {(2,4),(2,3)}

Тақырып. Экстремал графтар. Бағытталған графтар. Турнирлар. Рамсей теоремасы. Графтың метрикасы. Төбелерінің тәуелсіз жиыны. Клика.

1 нұсқа

1. Үшбұрыштары жоқ р- төбелі графтың қабырғаларының ең үлкен саны тең:

A) B) C) D) E)

2. Бағытталған графты күшті байланысты деп атаймыз, егер:

A) оның табаны(негізі) байланысты граф болса

B) екі төбесінен кем дегенде біреуінен екіншісіне жетуге болатын төбелер жұбы табылса

C) өзара жетуге болатын төбелер жұбы табылса

D) кез кеген төбелер жұбы өзара жетерлік болса

E) кез келген екі төбелерінің біреуі екіншісінен жетерлік болса

3. Егер бағытталған графтың доғаларының саны 10-ға тең болса және m, n –төбелерінің сәйкесінше кіру және шығу жарты дәрежелерінің қосындылары болса, онда:

A) n=m=5 B) n=m=10 C) n=m=15 D) m=n-1 E) n=m-1

4. (1,2),(1,3),(2,3) доғаларымен берілген бағытталған графтың төбелерінің сыбайлас матрицасы:

A) B) C) D) E)

5. (1,2),(1,6),(2,5),(3,4),(4,5) қабырғалары бар 6- төбелі графтың 3 және 6 төбелерінің ара қашықтығы тең...

6. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың диаметрі тең...

7. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1)) қабырғалары бар 6- төбелі графтың радиусы тең...

8. (1,2),(2,3),(3,4),(4,5),(5,6) қабырғалары бар 6- төбелік графтың орталық төбесі...

9. К_2n толық графтың диаметрі тең...

10. Куб графтың диаметрі тең...

11.(1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың төбелерінің келесі жиындарының қайсысы тәуелсіз болады:

A) {1,2,3} B) {1,2,4} C) {3,5,1} D) {3,5,2} E) {3,5}

12. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5 төбелі графтың клика болып табылатын жиынды көрсет:

A) {1,2,3} B) {1,2,4} C) {2,3,5} D) {2,3,4} E) {1,2,5}

13. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың төбелерді бүркитін жиынын көрсет:

A) {1,2} B) {2,5,4} C) {1,2,5} D) {2,4} E) {1,2,3}

14. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6 төбелі графтың доминантты жиынын көрсет:

A) {1,2} B) {1,3} C) {1,4} D) {1,5} E) {2,3}

15. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың қабырғаларының тәуелсіз жиының көрсет:

A) {(1,5),(2,5)} B) {(1,5),(2,3)} C) {(2,3),(3,4)}

D) {(2,3),(4,5),(1,5)} E) {(2,4),(2,3)}

2 вариант

1. р-төбелі байланыссыз графтың қабырғаларының ең үлкен саны тең:

A) B) C) +1

D) E)

2. Бағытталған графты күшті байланысты болады дейміз, сонда тек сонда, егер:

A) оның табаны – толық граф болса

B) оның табаны – эйлер граф болса

C) остовты бағыт табылса

D) остовты циклі бар бағыт табылса

E) оның табаны – гамильтон граф болса

3. Келесі доғалар тізбектерінің қайсысы 5- төбелі әлсіз байланысты графты анықтайды:

A) (1,2),(2,3),(3,4),(4,1) B) (1,2),(2,3),(3,4)

C) (1,2),(2,3),(3,1),(4,5) D) (1,2),(2,3),(3,4),(5,1)

E) (1,2),(2,3),(4,5)

4. (1,2),(1,3),(1,4),(3,2),(3,4),(4,2) доғаларымен берілген турнирдың остовты жолы келесі төбелерінің тізбегімен анықталады:

A) 1,2,3,4 B) 1,2,4,3 C) 1,3,2,4 D) 1,3,4,2

E) 1,4,3,2

5. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың 2 және 3 төбелерінің ара қашықтығы тең равно...

6. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың диаметрі тең...

7. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың 3- ші төбесінің эксцентриситеті тең...

8. (1,2),(2,3),(3,4),(4,5) қабырғалары бар 5- төбелік графтың орталық төбесі...

9. К_2n+1 толық графтың радиусы тең...

10. Октаэдрдр графтың диаметрі тең...

11.(1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың төбелерінің келесі жиындарының қайсысы тәуелсіз болады:

A) {1,2,3} B) {2,3,4} C) {2,3,5} D) {3,4,5} E) {3,5,6}

12. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6 төбелі графтың келесі жиыны клика болып табылады:

A) {1,2,3} B) {1,2,4} C) {2,3,5} D) {2,3,4} E) {1,2}

13. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың төбелерін бүркитін жиынын көрсет:

A) {1,5} B) {2,1,4} C) {1,4,5} D) {1,2,5} E) {1,2,6}

14. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6 төбелі графтың доминантты жиынын көрсет:

A) {1,2} B) {1,3} C) {1,4} D) {1,5} E) {2,3

15.(1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6- төбелі графтың қабырғаларының тәуелсіз жиының көрсет:

A) {(1,2),(3,5),(1,5)} B) {(1,2),(3,5),(4,6)}

C) {(1,2),(3,5),(4,5)} D) {(1,6),(3,5),(4,6)}

E) {(1,5),(4,6),(1,2)}

3 нұсқа

1. р – төбелі гамильтон болмайтын графтың қабырғаларының ең үлкен саны тең:

A) B) C) +1

D) E)

2. Бағытталған графты күшті біржақты байланысты болады дейміз, сонда тек сонда, егер:

A) оның табаны – толық граф болса

B) оның табаны – эйлер граф болса

C) остовты бағыт табылса

D) остовты циклі бар бағыт табылса

E) оның табаны – гамильтон граф болса

3. Келесі доғалар тізбектерінің қайсысы 5- төбелі күшті байланысты графты анықтайды:

A) (1,2),(1,3),(1,4),(1,5),(5,2)

B) (1,2),(1,3),(1,4),(1,5)

C) (1,2),(1,3),(4,1),(5,1)

D) (1,2),(1,4),(2,3),(3,5),(4,2),(5,1)

E) (1,2),(1,3),(4,1),(5,1),(5,2)

4. (1,2),(1,3),(1,4),(3,2),(3,4),(4,2) доғаларымен берілген турнирдың остовты жолы келесі төбелерінің тізбегімен анықталады:

A) 1,2,3,4 B) 1,2,4,3 C) 1,3,2,4 D) 1,3,4,2

E) 1,4,3,2

5. (1,2),(1,6),(2,5),(3,4),(4,5) қабырғалары бар 6- төбелі графтың 3 және 6 төбелерінің ара қашықтығы тең...

6. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың радиусы тең...

7. 1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың 4- ші төбесінің эксцентриситеті тең...

8. Егер байланысты графтың диаметрі 4-ке тең болса, онда радиусы тең бола алады:

A) 1 B) 2 C) 5 D) 6 E) 7

9. K_n,m толық екі бөлікті графтың радиусы тең...

10. Петерсен графтың диаметрі тең...

11. 8- төбелік G кубтық графтың b₀(G) төбелік тәуелсіздігінің саны келесі шартты қанағаттандырады:

A) b₀(G) = 1 B) b₀(G) = 2 C) b₀(G) ³ 2

D) b₀(G) = 3 E) b₀(G) ³ 3

12. Келесі графтардың қайсысының төбелік тәуелсіздігінің саны 1-ге тең болады:

A) K_n B) C_n C) P_n D) E)

13. (1,5),(2,3),(2,4),(2,5),(3,4),(4,5) қабырғалары бар 5- төбелі графтың төбелерін бүркитін жиыны...

14. (1,2),(1,5),(3,5),(4,5),(4,6),(6,1) қабырғалары бар 6 төбелі графтың ядросын көрсет A) {1,2} B) {1,3} C) {2,3,5} D) {2,3,4} E) {1,2,3}

15. К_р графтың қабырғалық тәуелсіздігінің саны тең:

A) p B) p(p-1)/2 C) p-1 D) E)

Дата добавления: 2015-09-27 | Просмотры: 756 | Нарушение авторских прав