MAX-CUT: вероятностное округление/Задачи/eupce-6-19 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
| − | {{проверено|}} | + | {{проверено|[[Участник:StasFomin|StasFomin]] 21:10, 17 декабря 2024 (UTC)}} |
{{bonus}} | {{bonus}} | ||
| − | [[File:eupce-6-19_2023-05-19_12-22-45_image0.png|480px]] | + | |
| − | [[File:eupce-6-19_2023-05-19_12-23-03_image0.png|480px]] | + | <latex> |
| − | + | Let $G=(V, E)$ be an undirected graph and suppose each $v \in V$ is | |
| + | associated with a set S(v) of $8r$ colors, where $r \geq 1$. | ||
| + | |||
| + | Suppose, in addition, that for each $v \in V$ and $c \in S(V)$ | ||
| + | there are at most $r$ neighbors $u$ of $v$ such that $c$ lies in $S(u)$. | ||
| + | |||
| + | Prove that there is a proper coloring of $G$ assigning to each vertex $v$ a color from its class $S(v)$ such that, for any edge $(u,v) \in E$, the colors assigned to $u$ and $v$ are different. | ||
| + | |||
| + | You may want to let $A_{u,v,c}$ be the event that $u$ and $v$ are both colored with color $c$ and then consider the family of such events. | ||
| + | </latex> | ||
| + | <!-- [[File:eupce-6-19_2023-05-19_12-22-45_image0.png|480px]] | ||
| + | [[File:eupce-6-19_2023-05-19_12-23-03_image0.png|480px]] --> | ||
[[Категория:Теоретические задачи]] | [[Категория:Теоретические задачи]] | ||
Текущая версия на 21:10, 17 декабря 2024
Проверено: StasFomin 21:10, 17 декабря 2024 (UTC)
