Mam problem z takim zadaniem. Czy mógłby ktoś pokazać jak należy to wykonać:
Na pewnym małym osiedlu wybudowano cztery domy (A,B,C,D). Czy mozna do kazdego
z tych domów dostarczyc energie elektryczna z elektrowni (E), wode z firmy wodociagowej
(W), gaz z firmy gazowej (G) oraz internet od dostawcy (I) tak, aby na planie zagospodarowania
terenu połaczenia (przewody/rury) nie przecinały sie?
Jezeli nie jest to mozliwe, to jaka jest najmniejsza liczba przeciec jaka musimy w tym
przypadku zaakceptowac?
W ramach rozwiazania narysowac odpowiedni graf.
Uwagi:
1. Kazdy dom jest podłaczony niezaleznym przewodem (kablem/rura) z odpowiednim
dostawca. Przewód taki zaczyna sie u dostawcy i konczy w domu. Nikt nie chce aby
(dla przykładu) woda do sasiada przechodziła przez jego dom!
2. Jezeli to konieczne, to w jednym miejscu moga sie przeciac tylko dwa przewody (rury/
kable).
