Поиск :
Личный кабинет :
Электронный каталог: Айрапетян, Л. Е. - О почти интервальных реберных раскрасках сеточных графов
Айрапетян, Л. Е. - О почти интервальных реберных раскрасках сеточных графов
Нет экз.
Электронный ресурс
Автор: Айрапетян, Л. Е.
О почти интервальных реберных раскрасках сеточных графов : студенческая научная работа
Издательство: [Б. и.], 2020 г.
ISBN отсутствует
Автор: Айрапетян, Л. Е.
О почти интервальных реберных раскрасках сеточных графов : студенческая научная работа
Издательство: [Б. и.], 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 – мерных кубов. В частности, он доказал, что если
Айрапетян, Л. Е.
О почти интервальных реберных раскрасках сеточных графов : студенческая научная работа / Российско-Армянский (славянский) университет. – Ереван : [Б. и.], 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 – мерных кубов. В частности, он доказал, что если