«И» «ИЛИ»  
© Публичная Библиотека
 -  - 
Универсальная библиотека, портал создателей электронных книг. Только для некоммерческого использования!
Ловас Ласло

Ласло Ловас 329k

(Lovasz Laszlo)

(09.03.1948)

  ◄  СМЕНИТЬ  ►  |▼ О СТРАНИЦЕ ▼
▼ ОЦИФРОВЩИКИ ▼|  ◄  СМЕНИТЬ  ►  
Википедия: Ласло Ловас (венг. Lovasz Laszlo, laslo lovas; род. 9 марта 1948) - венгерский математик, известный работами по комбинаторике, за которые он был награжден многими престижными премиями.
Член Национальной академии наук США (2012).
Родился в семье хирурга. Значительное впечатление на него оказали статья и личная встреча с Палом Эрдешем. Во время учебы в школе трижды выигрывал золотые медали на Международных математических олимпиадах (1964, 1965, 1966 года; в 1963 году получил серебряную), а его сын выиграл медаль в 2008 году.
Степень кандидата наук защитил в 1970 году в Венгерской академии наук, под руководством Тибора Галлаи (венг. Gallai Tibor). В течение 1990-х работал в должности профессора в Йельском университете и сотрудничал с исследовательским центром Microsoft до 2006 года. Затем вернулся в Будапештский университет, на должность директора Института математики.
Работы Ловаса в основном относятся к дискретной математике, включая теорию графов и комбинаторику (в первую очередь комбинаторную оптимизацию), а также к теоретической информатике. Он известен как соавтор имеющего многочисленные приложения алгоритма Ленстры - Ленстры - Ловаса (LLL-алгоритма). Ловас доказал теорему о совершенных графах (что принесло ему первоначальную известность), нашел емкость Шеннона пятиугольника (использованная им при этом оценка теперь известна как число Ловаса), доказал формулу для хроматического числа кнезеровского графа, сформулировал известную гипотезу о гамильтоновом цикле. Кроме того, он разработал многие другие алгоритмы, помимо LLL-алгоритма, доказал локальную лемму Ловаса, работал над теоремой PCP и популяризировал метод эллипсоидов. Также Ловас написал несколько известных книг по дискретной математике.
Был президентом Международного математического союза в 2007-2010 годах.
Получил грант от Европейского исследовательского совета в 2008 году. В 2008 году сделал пленарный доклад на Европейском математическом конгрессе. Избран иностранным членом Российской академии наук (2006), Шведской королевской академии наук (2007), почетным членом Лондонского математического общества в 2009 году. Находится в списке самых цитируемых исследователей ИНИ. С 2012 года является действительным членом Американского математического общества.
Соавтор 6 статей с Палом Эрдешем (благодаря этому обладает числом Эрдеша, равным 1).
:
...




  • Ловас Л... Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. (Matching theory, 1986) [Djv-Fax- 6.0M] [Pdf-Fax- 9.9M] Научное издание. Авторы: Ласло Ловас, Майкл Д. Пламмер (Laszlo Lovasz, Michael D. Plummer). Перевод с английского: Г.П. Гаврилов, В.В. Мартынюк, М.А. Никитина. Редактор перевода: Г.П. Гаврилова. Художник: Н.В. Зотова.
    (Москва: Издательство «Мир»: Редакция литературы по математическим наукам, 1998)
    Скан: AAW, OCR, обработка, формат Djv-Fax, Pdf-Fax: bolega, 2022
    • ОГЛАВЛЕНИЕ:
      Предисловие редактора перевода (5).
      Предисловие (7).
      Основные термины (31).
      1. Паросочетания в двудольных графах (37).
      1.0. Введение (37).
      1.1. Теоремы Кенига, Ф. Холла и Фробениуса (40).
      1.2. Алгоритм построения паросочетаний в двудольном графе: венгерский метод (49).
      1.3. Дефицит, избыток и кое-что из теории матроидов (56).
      1.4. Некоторые следствия из теорем о паросочетаниях в двудольных графах (69).
      2. Теория потоков (84).
      2.0. Введение (84).
      2.1. Теорема о максимальном потоке и минимальном разрезе (86).
      2.2. Потоковые алгоритмы (90).
      2.3. Потоко-эквивалентные деревья (109).
      2.4. Применение теории потоков в теории паросочетаний (117).
      2.5. Паросочетания, потоки и меры (125).
      3. Строение и размеры наибольших паросочетаний (134).
      3.0. Введение (134).
      3.1. Теорема Татта, лемма Галлаи и формула Бержа (135).
      3.2. Структурная теорема Галлаи - Эдмондса (147).
      3.3. Об исчислении барьеров (158).
      3.4. Достаточные условия существования паросочетаний заданого размера (166).
      4. Двудольные графы с совершенными паросочетаниями (177).
      4.0. Введение (177).
      4.1. Элементарные двудольные графы и их колосковая структура (178).
      4.2. Минимальные элементарные двудольные графы (184).
      4.3. Разложение на элементарные двудольные графы (196).
      5. Общие графы с совершенными паросочетаниями (202).
      5.0. Введение (202).
      5.1. Элементарные графы: элементарные свойства (204).
      5.2. Каноническое разбиение V(G) (210).
      5.3. Насыщенные графы и купола (220).
      5.4. Колосковая структура 1-расширяемых графов (238).
      5.5. Еще кое-что о факторно-критических и бикритических графах (263).
      6. Некоторые задачи теории графов, связанные с паросочетаниями (283).
      6.0. Введение (283).
      6.1. 2-паросочетания и 2-покрытия (283).
      6.2. 2-бикритические и регуляризуемые графы (288).
      6.3. Паросочетания, 2-паросочетания и свойство Кенига (291).
      6.4. Гамильтоновы циклы и 2-паросочетания (301).
      6.5. Задача китайского почтальона (304).
      6.6. Оптимальные цепи, циклы, соединения и разрезы (319).
      7. Паросочетания и линейное программирование (333).
      7.0. Введение (333).
      7.1. Линейное программирование и паросочетания в двудольных графах (346).
      7.2. Паросочетания и дробные паросочетания (354).
      7.3. Политоп паросочетаний (355).
      7.4. Хроматический индекс (368).
      7.5. Политопы дробных паросочетаний и полиэдры покрытий (375).
      7.6. Размерность политопа совершенных паросочетаний (376).
      8. Определители и паросочетания (392).
      8.0. Введение (392).
      8.1. Перманенты (395).
      8.2. Метод формальных переменных (401).
      8.3. Пфаффиан и число совершенных паросочетаний (405).
      8.4. Перечисление совершенных паросочетаний, базирующееся на вероятностном подходе (418).
      8.5. Многочлены, перечисляющие паросочетания (422).
      8.6. Еще о числе совершенных паросочетаний (435).
      8.7. Два приложения в физических науках (440).
      9. Алгоритмы построения паросочетаний (447).
      9.0. Введение (447).
      9.1. Алгоритм Эдмондса (448).
      9.2. Взвешенные паросочетания (460).
      9.3. Алгоритм, основанный на теореме Галлаи - Эдмондса (468).
      9.4. Алгоритм линейного программирования для построения паросочетаний (472).
      10. Задача об f-факторе (477).
      10.0. Введение (477).
      10.1. Принципы сведения (479).
      10.2. Структурная теория f-факторов (482).
      10.3. Задача о наборах степеней вершин графов (501).
      11. Матроидные паросочетания (507).
      11.0. Введение (507).
      11.1. Формулировки задачи о матроидных паросочетаниях (508).
      11.2. Основная теорема о полиматроидном паросочетаний (527).
      11.3. Паросочетания в специальных полиматроидах (536).
      12. Вершинные упаковки и покрытия (546).
      12.0. Введение (546).
      12.1. Критические графы (548).
      12.2. Политопы вершинных упаковок (562).
      12.3. Паросочетания в гиперграфах (573).
      12.4. Вершинные упаковки в графах, не содержащих клешней (579).
      Литература (593).
      Предметный указатель (637).
      Указатель обозначений (645).
ИЗ ИЗДАНИЯ: Книга известных специалистов по комбинаторике (Венгрия, США), охватывающая разнообразные области дискретной математики - задачу о коммивояжере, теорию потоков, модель Изинга ферромагнетизма, теорию матроидов и линейное программирование. В ней представлены как классические методы и алгоритмы, так и новые подходы и конструкции: NP-полнота, теоремы Бержа, Татта, Галлаи - Эдмондса и др. Книга имеет явно энциклопедический характер, отличается прикладной направленностью и требует лишь минимальной математической подготовки.
Для математиков разных специальностей - геометров, алгебраистов, специалистов по дискретной математике и кибернетике, для инженеров и программистов, а также аспирантов и студентов технических и экономических вузов.