|
|
Название: |
Основы теории графов |
|
| Автор: |
Зыков А.А. (Загрузил Denis aka Rock Lee) |
| Категория: |
Математика
|
| Дата добавления: |
12.01.2009 |
| Скачиваний: |
704 |
| Рейтинг: |
|
| Описание: |
Теория графов - важный раздел современной математики как с точки зре ния внутренних стимулов ее развития, так и для разнообразных и многочисленных приложений Практическая роль графов особенно возросла за последнее время в связи с проектированием различных АСУ и вычислительных устройств дискретного действия. В теоретическом же плане помимо давнишних связей с комбинаторной топологией и геометрией наметились существенные сдвиги на стыке теории графов с алгеброй, математической югикой, лингвистикой, теорией игр и общей теорией систем
Во многих университетах и других учебных заведениях читаются лекции по теории графов либо в виде отдельного курса, либо как часть более общего Кроме того, графы часто приходится самостоятельно изучать инженерам, физикам, химикам, биологам, экономистам, социологам и др , сталкивающимся с ними в процессе своей деятельности Однако задачу достаточно полного, систематического и в то же время доступного освещения современной теории графов в отечественной литературе пока нельзя (.читать удовлетворительно решенной, а совершенно необходимое учебно-шравочное пособие отсутствует совсем. Предлагаемая книга имеет целью восполнить этот пробел в элементарной части, составляющей фактический материал теории графов и ке опирающейся существенным образом на другие разделы математики (за исключением линейной алгебры и элементов топологии в гл 3); для более глубокого изучения современной теории графов она может служить лишь необходимым введением
Что же такое граф? Начнем не с формального определения, а с поясняющего примера
На рис О 1 изображен граф, вершинами которого служат нумерованные кружки, а ребрами — линии (со стрелками или без), соединяющие некоторые из этих кружков Ребро а ориентированное (направленное) оно соединяет вершину © с вершиной ф, но не соединяет © с © (и вообще не соединяет никакую другую пару вершин), к такому типу ребер, называемых дугами, относятся также e,f,g. Ребро h неориентированное (ненаправленное) оно одновременно соединяет как вершину ©с вершиной©, так и © с©, к ребрам этого типа, называемым еще звеньями, относятся также ( и у Наконец, каждое из ребер Ь, с, d, к является петлёй -шединяет некоторую вершину с ней же, вводить ориентацию такого ребра мы не будем
О ребрах a,b,e,f,g,/i говорят, что они инцидентны вершине©, а о вершине © - что она инцидентна каждому из этих ребер, в отношении Дут можно еще уточнить дуги а, е и / исходят из вершины©, а дуга g |
|
|
|
