Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
1.Defnicjagrafuiprzykładyzastosowań
Przedstawionyproblemjestmałyirozwiązanieotrzymamymetodąintuicyjną.Do
przeprowadzeniawszystkichegzaminówpotrzebnesątrzyterminy.Wkażdymztermi-
nówmogąsięjednocześnieodbywaćnastępująceegzaminy:{1,6,8},{4,5,7},{2,3}.
Problem1.;.Serwisgwarancyjny
Serwisgwarancyjnymaczterypojazdyspecjalistyczne{1,2,3,4}orazczteryekipy
specjalistów{a,b,c,d}.Serwisotrzymałdowykonaniasiedemnaprawwróżnychmiej-
scowościach.Każdanaprawawymagaodpowiedniejekipyiodpowiedniegopojazdu,co
przedstawiagrafGnarys.1.13a.Zakładamy,żejednaekipa,używającjednegopojazdu,
możejednegodniawykonaćdokładniejednąnaprawę.Opracujtakiplannaprawwpo-
szczególnychdniach,abywszystkienaprawyłącznietrwałyjaknajmniejsząliczbędni.
Rys.1.13.Przydziałzadańdlaserwisu
Rozwiązanie
Jednązmetodrozwiązaniajestprzydzielenieminimalnejliczbykolorówkrawędziom
grafu,takabykrawędzieowspólnymwierzchołkumiałyróżnekolory.Przedstawio-
notonarys.1.13b-nkolory”krawędzisąwyróżnioneliczbamiwnawiasachokrą-
głych.Naprawyodpowiadającekrawędziomoróżnychkolorachmogąbyćwykonane
tegosamegodnia,akrawędzieoidentycznychkolorachodpowiadająposzczególnym
dniomnaprawy.Przeprowadzenienaprawmożebyćwykonanewciągu3dni.Więcej
wiadomościnatematkolorowaniakrawędzigrafumożnaznaleźćwrozdziale16.
Problem1.9.Obsadastanowisk
FirmanPrzyszłość”ogłosiłanabórpracownikównaczterystanowiska(nazwijmyje
a,b,c,d)wymagająceokreślonychumiejętności.Zgłosiłosiępięciukandydatów
