Автор: Пользователь скрыл имя, 08 Марта 2012 в 19:00, реферат
В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации.
ПОДГРАФЫ, ОРИЕНТИРОВАННЫЕ ПОДГРАФЫ И СВЯЗНОСТЬ
(АНАЛОГИИ И ОТЛИЧИЯ)
Пусть D=(V, A) - орграф | Пусть G=(V, E) - граф |
Орграф D называется сильно связным (сильным, категории связности 3), если для каждой пары вершин ui и uj в Dui достижима из ujи ui достижима из ui. | Граф G называется связным, если каждая пара вершин ui и uj в Gсвязана цепью. |
Орграф D называется слабо связным (слабым, категории связности 1), если каждая пара вершин ui и uj в D соединима (полупутем). | Аналогия - см. выше
|
Орграф D называется односторонне связным (односторонним, категории связности 2), если для каждой пары вершин ui и ujв D либо ui достижима из uj , либо uj достижима из ui . | Аналогия - см. выше
|
Подграфом в D называется орграф (W, B), в котором W V, B A. | Подграфом в G называется граф (W, F), в котором W V, F E. |
Порожденным подграфом в D называется подграф (W, B), в котором B содержит все дуги из A, соединяющие вершины в W. | Порожденным подграфом в G называется подграф (W, F), в котором F содержит все ребра из E, соединяющие вершины в W. |
Сильной компонентой в D называется максимальный сильно связный (порожден-ный) подграф. | Компонентой (связности) в G называется максимальный связный (порожденный) подграф. |
Взвешенный граф, взвешенный орграф - граф (орграф), каждому ребру которого приписан некоторый вес.
Знаковый граф, знаковый орграф - граф (орграф), каждому ребру которого приписан некоторый знак.
Знак пути, цепи, замкнутого пути, замкнутой цепи, контура, цикла и т.д. определяется как произведение знаков входящих в них дуг или ребер, если знак плюс заменить на +1, а знак минус на -1. Очевидно, что путь, цепь и т.д. имеют знак минус, если число дуг или ребер, содержащихся в них, нечетно, иначе они имеют знак плюс.
Пример:Хейдер изучал задачи из области социологии малых групп людей (Heider F. Attitudes and Cognitive Organization. - J. of Phych., 21, 1946, p. 107-112).
Его результаты - полный обзор вариантов знаковых графов для группы из трех человек в условиях явно выраженной выраженной симпатии / антипатии представлены на рисунках.
Группы из трех лиц по Хейдеру психологически
сбалансированные
несбалансированные
Анализ этого и огромного количества других примеров из самых разных областей человеческой деятельности привел Картрайта и Харари (Cartwright D. and Harary F. Structural Balance: A Generalization of Heider's Theory. - Psych. Rev., 63, 1956, p. 277-293) к следующей математической модели баланса:
Малая группа является сбалансированной, если представляющий ее знаковый граф сбалансирован.
Знаковый граф называется сбалансированным, если каждый цикл в нем положителен.
Теорема о структуре (теорема Харари о балансе)
Для знакового графа G=(V,E) следующие утверждения эквивалентны:
Последнее утверждение называют также критерием баланса.
Применение графов.
Распределение ресурсов на медицинские нужды в Британской Колумбии
[1] - влияние окружающей cреды; [2] - возрастная структура населения; [3] - численность населения; [4] - пособие при заболевании; [5] - выявление и исследование проблем в области здравоохранения; [6] - доступность медицинского обслуживания; [7] - затраты времени врачом; [8] - медицинские учреждения; [9] - передача медицинских обязанностей другим лицам; [10] - расходы. (Kane J., Thompson W. and Vertinsky I. Health Care Delivery: A Policy Simulation, Socio-Econ. Plan. Sci., 6, 1972, p. 283-293).
Анализ проблемы очистки прибрежной зоны
[1] - допустимая посещаемость пляжа; [2] - действительная посещаемость пляжа; [3] - удовлетворение потребностей города; [4] - населенность города; [5] - необозначенная граница прибрежной зоны; [6] - капиталовложения на содержание пляжей. (Сoady S.K., Johnson G.P. and Johnson J.M. Effectively Conveying Results: A Key to the Usefullness of Technology Assesment, Mimeographed, Institute for Water Resources, Corps of Engineers. - Paper delivered at the First International Congresss on Technology Assessment, The Hague, M31,1973).
Анализ проблем потребления электроэнергии.
(Roberts F.S. Signed Diagraphs and the Growing Demand for Energy, Environment and Planning, 3, 1971, p. 395-410).
1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
2. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
3. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.
4. Оре О. Теория графов. – М.: Наука, 1980.
5. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. – М.: Наука, 1978.