Практикум по дисциплине «Дискретная математика», Теория графов.

Содержание

Введение                                                                                                             

1. Краткий перечень основных понятий теории графов                           

1.1. Общие понятия                                                                                          

1.2. Понятия смежности, инцидентности, степени                                   

1.3. Маршруты и пути                                                                                      

1.4. Матрицы смежности и инцидентности                                                 

1.5. Связность. Компоненты связности                                                        

1.6. Матрицы достижимости и связности                                                    

1.7. Расстояния в графе                                                                                  

1.8. Образ и прообраз вершины и множества вершин                            

1.9. Нагруженные графы                                                                               

1.10. Деревья и циклы                                                                                    

2. Решение контрольных задач                                                                    

2.1. Компоненты сильной связности ориентированного графа            

2.2. Расстояния в ориентированном графе                                                

2.3. Минимальный путь в нагруженном ориентированном графе       

2.4. Эйлеровы циклы и цепи                                                                         

2.5. Минимальное остовное дерево                                                            

2. 6. Задача о коммивояжёре                                                                       

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