Awans (omówienie)

07.06.2010

Niech P będzie zbiorem pracowników, a S stanowisk. Niech też między pewnym p z P a s z S istnieje krawędź wtedy i tylko wtedy, gdy para (p,s) figuruje na liście potencjalnych awansów. Widać, że powstały graf jest dwudzielny. Ponieważ jeden pracownik może być awansowany tylko na jedno stanowisko oraz na jedno stanowisko może być awansowany tylko jeden pracownik, podgraf pana Henryka oraz podgraf asystenta są skojarzeniami (skojarzenie to taki podgraf, w którym każdy wierzchołek ma co najwyżej jednego sąsiada).

Wierzchołek nazwiemy potrzebnym, jeśli szukane skojarzenie wymaga, żeby był on pokryty (potrzebne są zatem wierzchołki z S z listy pana Henryka oraz wierzchołki z P z listy asystenta). Wyrzućmy wszystkie krawędzie, których nie uwzględnił ani pan Henryk ani asystent - nie będą one w ogóle potrzebne. Pozostałe krawędzie tworzą pewnien graf G. Łatwo zauważyć, że stopień każdego wierzchołka w G jest nie większy niż 2. Z tego zaś wynika (łatwe ćwiczenie), że graf G składa się ze ścieżek oraz cykli.


Zajmijmy się najpierw cyklami. Łatwo pokazać, że każdy cykl w grafie dwudzielnym jest parzystej długości. Jeśli więc weźmiemy do rozwiązania co drugą krawędź z tego cyklu, wszystkie jego wierzchołki będą pokryte - niezależnie od tego, czy są potrzebne czy nie. To gwarantuje nam, że żadnego potrzebnego wierzchołka nie pominiemy.


Co do ścieżek o parzystej liczbie wierzchołków - robimy dokładnie to samo co dla cykli. Bierzemy do wyniku co drugą krawędź (zaczynając od pierwszej). W ten sposób na pewno wszystkie wierzchołki ze ścieżki zostaną pokryte.
Problem, przynajmniej na pierwszy rzut oka, mogą stwarzać jedynie ścieżki o nieparzystej liczbie wierzchołków. Rozważmy pierwszy wierzchołek na tej ścieżce. Jeśli nie jest on potrzebny, bierzemy do wyniku co drugą krawędź począwszy od drugiej na ścieżce. W ten sposób pokryte będą na pewno wszystkie potrzebne wierzchołki. Jeśli zaś pierwszy wierzchołek jest potrzebny, to ostatni na pewno nie (bo jest tego samego rodzaju, tzn. P lub S, co wierzchołek pierwszy, i nie sąsiaduje z krawędzią tego rodzaju, co pierwszy). Widać to na poniższym rysunku (małe litery oznaczają wierzchołki niepotrzebne, duże potrzebne, 1 to krawędź pochodząca z listy pana Henryka, 2 z listy asystenta):

S --- 1 --- P --- 2 --- S --- 1 --- P --- 2 --- s

Prawe s nie jest potrzebne, bo nie sąsiaduje z krawędzią typu 1. Znaleźliśmy zatem skojarzenie, o które chodziło w zadaniu - pokryte zostały wszystkie potrzebne wierzchołki.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com