Электронный каталог Фундаментальной
библиотеки ФГБОУ ВО МГППУ

👓
eng|rus
Фундаментальная библиотека Московского
государственного психолого-педагогического
университета

Адрес: г. Москва, ул. Сретенка, д. 29
Телефон: 8 (495) 607-23-40
Часы работы: пн-пт — 9:00—20:00; сб — 10:00—18:00
bib_logo

Поиск :

  • Новые поступления
  • Простой поиск
  • Расширенный поиск

  • Авторы
  • Издательства
  • Серии
  • Тезаурус (Рубрики)

  • Учебная литература:
      • Список дисциплин

    • Помощь

    Личный кабинет :


    Электронный каталог: Айрапетян, Л. Е. - О почти интервальных реберных раскрасках сеточных графов

    Айрапетян, Л. Е. - О почти интервальных реберных раскрасках сеточных графов

    Нет экз.
    Электронный ресурс
    Автор: Айрапетян, Л. Е.
    О почти интервальных реберных раскрасках сеточных графов : студенческая научная работа
    Издательство: [Б. и.], 2020 г.
    ISBN отсутствует

    полный текст

    На полку На полку


    Электронный ресурс

    Айрапетян, Л. Е.
    О почти интервальных реберных раскрасках сеточных графов : студенческая научная работа / Российско-Армянский (славянский) университет. – Ереван : [Б. и.], 2020. – 29 с. : табл.,схем. – URL: https://biblioclub.ru/index.php?page=book&id=595621. – Режим доступа: электронная библиотечная система «Университетская библиотека ONLINE», требуется авторизация . – Библиогр.: с. 28-29. – На рус. яз.

    Эффективность применения методов теории графов для исследования задач о расписаниях хорошо известна. Понятие интервальной раскраски ребер было впервые введено А.С. Асратяном и Р.Р. Камаляном в 1987 году, и было мотивированно проблемой поиска компактных школьных расписаний, т.е. не имеющих “окон”. Правильная раскраска графа G цветами 1, 2, ... t называется интервальной t – раскраской, если для любой вершины v ∈ V(G), инцидентные ей ребра раскрашены последовательными цветами, и любым цветом i (1 ≤ i ≤ t) раскрашено хотя бы одно ребро графа G. Они доказали, что если G является интервально раскрашиваемым, то χ(G) = Δ(G). Кроме того, если граф G является г – регулярным, то граф G имеет интервальную раскраску тогда и только тогда, когда граф G имеет правильную г -раскраску. Это означает, что задача “Является ли данный r – регулярный (r ≥3) граф интервально раскрашиваемым графом или нет?” является NP -полной задачей. А.С. Асратян и Р.Р. Камалян также доказали, что если граф без треугольников G имеет интервальную t - раскраску, тогда t ≤ |V(G)| - 1. Р.Р. Камаляном исследованы интервальные раскраски полных двудольных графов и деревьев. В частности, он доказал, что полный двудольный граф Km,n имеет интервальную t - раскраску тогда и только тогда, когда m + n - (m, n) ≤ t ≤ m + n - 1, где (m, n) - наибольший общий делитель чисел m и n. П.А. Петросян исследовал интервальные раскраски полных графов и n – мерных кубов. В частности, он доказал, что если


    © Все права защищены ООО "Компания Либэр" , 2009 - 2025  v.20.159