|
|
| (не показано 17 промежуточных версий 2 участников) |
| Строка 3: |
Строка 3: |
| | </latex> | | </latex> |
| | | | |
| − | Алгоритм: возьмем граф G=(V,E); результирующее множество R — пустое.
| + | <!--Вообще-то, решения уже есть--> |
| | | | |
| − | 1) Выберем произвольное ребро (u, v) из E, <latex>u \in V, v \in V</latex>
| + | [[Категория:Решенные задачи]] |
| − | | + | [[Категория:Теоретические задачи]] |
| − | 2) Добавим это ребро в множество R
| + | |
| − | | + | |
| − | 3) Удалим для u, v все инцидентные этим вершинам ребра из E.
| + | |
| − | | + | |
| − | повторяем 1-3 пока не останется ребер в E; получим R — искомое паросочетание.
| + | |
| − | | + | |
| − | Доказательство 1/2-точности данного приближенного алгоритма:
| + | |
| − | Для оптимального паросочетания R* любое ребро из исходного графа инцедентно ребрам из R*(или содержится в R*).
| + | |
| − | Пусть «нет» и существует ребро (u, v) не из R* и не инцедентное ребрам из R* — тогда это ребро можно добавить к R*, то-есть R* не максимальное по включению(<latex>R* \subset (R^* \cup(u, v))</latex>).
| + | |
| − | Значит все ребра из R имеют общую вершину с ребрами из R*, так как количество вершин R* = 2|R*| и ребра из R содержат минимум по одной вершине, и в одной вершине может быть максимум одно ребро из R, то <latex>|R| <= 2|R*|</latex> , чтд.
| + | |
| − | | + | |
| − | ps: Вообще, мне кажется, если следовать определению точно, то точность = 2 и точность 1/2 была бы если бы <latex>|R| <= 1/2|R*|</latex>, но это не возможно так как R* - минимум.
| + | |
| − | </big>
| + | |
| − | [[Category:На проверку]] | + | |
| − | <!--Вообще-то, решения уже есть-->
| + | |