Қазақстан республикасының білім және ғылым министірлігі



жүктеу 21,8 Mb.
бет132/214
Дата09.01.2018
өлшемі21,8 Mb.
#7265
түріМазмұндама
1   ...   128   129   130   131   132   133   134   135   ...   214

8-өзіндік жұмыс. Граф сандары. Графтардағы маршруттар.

а) Семестрлік жұмыста құрылған G1U G2 жәнеG1хG2 графтары үшін:



  • Цикломатикалық санды;

  • Хроматикалық санды;

  • Диаметр, радиус, центрді табыңыз.

Бұл графтардың планарлы және эйлер графы болуын тексеріңіз.Барлық қаңқалы ағаштарды белгілеңіз.

б) 7 Семестрлік жұмыстағы графы үшін төмендегілерді көрсетіңіз:



  • Тұйық емес маршрут, бірақ шынжыр емес;

  • Қарапайым емес шынжар;

  • Қарапайым шынжыр;

  • Тұйық маршрут, бірақ цикл емес;

  • Қарапайым емес цикл;

  • Қарапайым цикл;

Бірінші төбеден шығатын ұзындығы 2-ге тең барлық маршруттарды және ұзындығы 2-ге тең маршруттың матрицасын табыңыз.


Қазақстан Республикасының Білім және ғылым министрлігі

Ш.Уәлиханов атындағы Көкшетау мемлекеттік университеті

050504-Есептеу техникасы және ПҚ мамандығы



Дискреттік математика пәні бойынша

Емтихан сұрақтарының

ТІЗІМІ

Көкшетау-2007 ж.



1. Жиындар үшін де Морган заңын тұжырымдаңыз?

2. Универсум деген не?

3. Қиылысу операциясын кескіндейтін Эйлер-Венн диаграммасын сызыңыз?

4. Кортеж деген не?Екі жиынның Декарт көбейтіндісі деп нені айтамыз?

5. Ақырлы жиынның қуаты деген не? Қандай жиынды саналымды дейміз?

6. Екі саналымды екі жиынның бірігуінің қуаты қандай?

7. Жазықтықтың барлық нүктелерінің жиынының қуаты қандай?

8. Қуаты үшке тең жиын элементтерінен қанша бинарлы қатынас құруға болады?

9. Араларында өзара бір мәнді сәйкестік болуы үшін екі жиынның қуаттары қандай болуы керек?

10.Берілген жиында рефлексивті ,симметриялы емес, транзитивті қатынастар құрыңыз?

11.Квадрат пен кесінді нүктелерінің жиыны эквивалентті екенін дәлелдеңіз?

12. Бір жиынды екінші жиынға түрлендіретін функциялар саны қанша?

13.Жиынды екінші жиынға түрлендіретін инъективті бейнелеулері қанша?

14. Кантор теоремасын дәлелдеңіз?

15. Иррационал сандар жиынының қуаты қандай?

16. Жиында қандай қатынас рефлексивті деп аталады? Транзитивті қатынасқа мысал келтіріңіз?

17. Антирефлексивті, антисимметриялы және транзитивті қатынастар қалай аталады?

18. Екі түзудің перпендикуляр болу қатынасы эквивалентті деуге бола ма?

19. Жиындар арасындағы қандай сәйкестік бейнелеу деп аталады?

20. Қандай бейнелеу функционалды деп аталады?

21. Реті қатаң емес қатынас қандай қасиетке ие?

22. Жиынды бөліктеу деген не?

23. Қандай функция логикалық деп аталады?

24. Екі айнымалыда тәуелді қанша логикалық функция бар?

25. Эквиваленттіліктің терістеуі қандай функция?

26. Логикалық функцияда қандай айнымалы жалған деп аталады?

27. Үшіншіні шығару және қарама қарсылық заңдарын атаңыз?

28. Логикалық функцияның қандай түрі ДҚФ деп аталады?

29. Қандай екі функция эквивалентті деп аталады?

30. Қандай функция басқа логикалық функцияға түйіндес деп аталады?

31. Қандай логикалық функцияда МКҚФ жоқ?

32. Өзіне өзі түйіндес деп қандай логикалық функцияны айтады?

33. Анықталмаған коэффициенттер әдісімен логикалық функциядан Жегалкин полиномын қалай анықтайды?

34. Қандай логикалық функция сызықты деп аталады?

35. Логикалық функцияның МДҚФ қалай анықтайды?

36. Үш айнымалыдан тәуелді логикалық функцияның анықталу облысының қуаты қандай?

37. Неше элементер логикалық функциялар бірді сақтайды?

38. Нөлді сақтайтын барлық элементар функцияларды атаңыз?

39. Қандай монотонды логикалық функция нөлді сақтамайды?

40. Қандай логикалық функциялар жүйесі толық деп аталады?

41. Бір функциядан тұратын функционалды толық жүйені атаңыз?

42. Функционалдың толықтық туралы Пост функциясын атаңыз?

43. Функциялардың қандай класы тұйық деп аталады?

44.Комбинаторикадағы қосу және көбейту ережесін атаңыз?

45. Қандай таңдамалар орналастыру, теру деп аталады?

46. Түрлі таңдамалар саны қандай формулалармен есептеледі?

47. Қандай бөліктеу саны Стирлинг санын пайдалану арқылы есептеледі?

48. «Тәртіпсіздік»,«Кездесу» есептеріне сипаттаңыз?

49. Жиын элементерінің алмастыру санын қалай есептейді?

50. Бағытталған, бағытталмаған граф анықтамалары қандай?

51. Графтардың берілу тәсілдерін атаңыз?

52. Графтың қандай қабырғалары (доғалары) сыбайлас деп аталады?

53. Графтың қандай қабырғалары (доғалары) бір-біріне инцидентті болады?

54. Төбенің дәрежесі деген не?

55. Қандай граф көп граф деп аталады?

56. Толық графта әр төбенің дәрежесі неге тең?

57. Графтың цикломатикалық санын қалай есептейді?

58. Цикломатикалық сан нені көрсетеді?Цикломатикалық саны нөлге тең граф қалай аталады?

59. Графтармен орындалатын операцияларды атаңыз?

60. Қандай граф толық графтың қосымшасы болады?

61. Граф маршрут, тұйық маршрут дегендер не?

62. Шынжыр, қарапайым шынжыр, цикл, қарапайым цикл дегендерге анықтама бер?

63. Қандай граф байланысты деп аталады?

64. Графтың бөлігі, ішкі граф, суграф деп қандай графтарды айтады?

65. Ағаш деп қандай графты айтады?Ағаштың қаңқасы (каркас) деп нені айтады?

66. Графтарда ара қашықтық деп нені түсінеміз?

67. Графтың диаметрі, радиусы, центрі дегендер не?

68. Қандай граф қаныққан деп аталады?

69. Ең кіші салмақты қаңқалы ағашты анықтаудың Краскал алгоритмі қандай?

70. Графтың цикломатикалық саны деген не?Қандай граф бір хроматикалы?

71. Толық графтың хроматикалық сан неге тең?

72. Бағытталмаған байланысты нагруженный графтың екі төбесінің ең қысқа аралығын анықтайтын 73. Форд алгоритмін сипаттаңыз?

74. Қандай циклдер Эйлер циклы деп аталады?

75. Эйлер графы болу үшін жеткілікті және қажетті шартты атаңыз?

76. Гамильтон шынжыры, Гамильтон циклі деп нені айтады?

77. Коммивояжер туралы есепке сипаттама беріңіз?

78. Графта Гамильтон циклі бар болудың жеткілікті шарты қандай?

79. Қандай граф жазық деп аталады?

80. Қандай граф транспорттық желі деп аталады?

81. Доғаның жіберу мүмкіндігі деп нені айтады?

82. Транспорттық желіде қандай доғалар қаныққан деп аталады?

83. Желіде нені ағын деп атайды?

84. Қандай ағын толық деп аталады?

85. Желінің қандай төбелері бастауы, соңы деп аталады?

86. Желідегі ең үлкен ағынды анықтайтын Форд-Фалкерсон алгоритмін сипаттаңыз?

Глоссарий





Жаңа ұғымдар

Мазмұны

1

Жиын

Табиғаты кез келген болатын элементтер жиынтығы.

2

А жиыны В жиынының ішкі жиыны деп аталады.

Егер А жиынының барлық элементтері В-ға жатса:

.

3

А мен В жиындары тең

Егер және болса, болып белгіледі.

жүктеу 21,8 Mb.

Достарыңызбен бөлісу:
1   ...   128   129   130   131   132   133   134   135   ...   214




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау