Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
В теории графов теорема Кёнига , доказанная Денешем Кёнигом в 1931, утверждает эквивалентность задач нахождения наибольшего паросочетания и наименьшего вершинного покрытия в двудольных графах. Независимо была открыта, в том же 1931, Йенё Эгервари в несколько более общем виде для случая взвешенных графов.
Я́нош Ко́рнаи — венгерский экономист, в 1978 году президент Эконометрического общества, автор эффекта мягких бюджетных ограничений.
Де́неш Га́бор — венгерский физик, лауреат Нобелевской премии по физике в 1971 году «за изобретение и развитие голографического метода».
Пал Э́рдёш — венгерский математик, один из наиболее продуктивных математиков XX века. Работал в самых разных областях современной математики: комбинаторика, теория графов, теория чисел, математический анализ, теория приближений, теория множеств и теория вероятностей. Лауреат множества математических наград, включая премию Вольфа (1983/1984). Основатель премии Эрдёша.
Альфре́д Ре́ньи — венгерский математик.
Роберт Эндре Тарджан — американский учёный в области теории вычислительных систем.
Премье́р-мини́стр Ве́нгрии — глава правительства Венгрии. Избирается парламентом по предложению президента республики. Премьер-министром назначается лидер партии, получившей на выборах большинство мест в парламенте либо партии, способной сформировать парламентскую коалицию.
Ласло Ловас — венгерский математик, известный работами по комбинаторике, за которые он был награждён многими престижными премиями.
Липот Фейер — венгерский математик.
Эндре Семереди — венгерский и американский математик, работающий в областях комбинаторики и теоретической информатики. Лауреат Абелевской премии 2012 года «за фундаментальный вклад в дискретную математику и теорию информатики, и в знак признания глубокого и долгосрочного вклада в аддитивную теорию чисел и эргодическую теорию». Имеет число Эрдёша, равное 1.
Дьёрдь Се́кереш — венгерский и австралийский математик, кавалер ордена Австралии.
Кёниг, Иога́нн Самуэ́ль — швейцарский математик и механик. Член-корреспондент Парижской АН (1740), член Берлинской АН (1749), Лондонского Королевского общества (1750), Гёттингенской АН.
Денеш Беринкеи — венгерский юрист и политик, который был премьер-министром при режиме Михая Каройи в течение двух месяцев в 1919 году.
В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины.
Пал Туран — венгерский математик, основатель экстремальной теории графов.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр, ни нечётных антидыр. Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нейла Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
Ро́жа Пе́тер — венгерский математик и логик. Автор теории рекурсивных функций.
Теорема Петерсена — одна из самых ранних теорем теории графов, названная в честь Юлиуса Петерсена. Определение теоремы может быть сформулировано следующим образом:
Теорема Петерсена. Любой кубический двусвязный граф содержит в себе совершенное паросочетание.
Медиафайлы на Викискладе
