РГР_ПО_ДИСКРЕТКЕ

Содержание

Введние……………………………………………….……..………3

Элементы теории графов……………………………….…….4
1. Основные понятия теории графов……………...…………….4
2. Способы задания графов………………………………………10
3. Связность графов…………………………………………13
4. Изоморфизм графов………………………………………19
5. Планарные графы…………………………………………20
6. Эйлеровы графы…………………………………….…….21
7. Гамильтоновы графы………………………………….….23
8. Деревья……………………………………………….……24

Контрольные вопросы к разделу……………………………..28

Задачи и алгоритмы………………………………………28
1. Алгоритмы поиска………………………………………..28
2. Раскраска в графах………………………………………..31
3. Алгоритмы построения деревьев………………………..35
4. Алгоритмы поиска путей…………………………….…..40
  1. Алгоритм Дийкстры……………………………..…..41
  2. Алгоритм Форда………………………….……….….42
  3. Алгоритм Флойда……………………………….……47
5. Потоковые алгоритмы……………………………………49
  1. Определения и постановки задач……………………49
  2. Алгоритм поиска максимального потока……………55
  3. Алгоритм поиска потока минимальной стоимости...60
  4. Динамический поток……………………………….…65
  5. Алгоритм дефекта…………………………………....68

Контрольные вопросы к разделу……………………………77

Задачи для самостоятельного решения……………………..78

Литература…………………………………………………….99

3

4

5

6

7

8

9

100

10

99

11

98

12

97

13

96

14

95

15

94

16

93

17

92

18

91

19

90

20

89

21

88

22

87

23

86

24

85

25

84

26

83

27

82

28

81

29

80

30

79

31

78

32

77

33

76

34

75

35

74

36

73

37

72

38

71

39

70

40

69

41

68

42

67

43

66

44

65

45

64

46

63

47

62

48

61

49

60

50

59

51

58

52

57

53

56

54

55

Содержание