szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 22 gru 2015, o 16:56 
Użytkownik

Posty: 20
Lokalizacja: Dęblin
Witam.
Ma ktoś pomysł jak przerobić szachownicę z ścianami, na której stawiamy wieże tak aby się nie biły nawzajem, na sieć przepływową? Chodzi mi o to co uznać za wierzchołki i wartości krawędzi co mają oznaczać? W jaki sposób określić dzięki sieci przepływowej maksymalną ilość wieży jaką można postawić na takiej szachownicy (ściany stawiamy dowolnie, rozmiar również jest dowolny)?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 22 gru 2015, o 21:02 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Niech X będzie zbiorem pól szachownicy, C\subset P(X) – zbiorem kolumn (jeśli kolumna jest przedzielona ścianą, to traktujemy ją jako dwie kolumny), R\subset P(X) – zbiorem wierszy. Ustalmy ponadto źródło i ściek: s,e\not\in C\cup X\cup R.

Definiujemy zbiór wierzchołków grafu:

V=\{s\}\cup C\cup X\cup R\cup \{e\}

i zbiór krawędzi

E = (\{s\}\times C) \cup \{(c,x):c\in C, x\in c\} \cup \{(x,r): r\in R, x\in r\}\cup (R\times \{e\}).

Każda krawędź niech ma przepustowość równą 1.

Rozwiązanie ma tę wadę, że działa tylko na szachownicy dwuwymiarowej. Jest też nie do końca ścisłe, ale to można poprawić poprzez urozłącznienie zbiorów C, X, R.
Góra
Mężczyzna Offline
PostNapisane: 22 gru 2015, o 22:03 
Użytkownik

Posty: 20
Lokalizacja: Dęblin
A do pól szachownicy zliczać także te pola na których są ściany?
Góra
Mężczyzna Offline
PostNapisane: 23 gru 2015, o 20:05 
Użytkownik

Posty: 5105
Lokalizacja: 52°16'37''N 20°52'45''E
Jakie to ma znaczenie? Jak dodasz wierzchołki izolowane do grafu, to nic się nie zmieni.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Znaleźć najkrótszą spójną sieć  max123321  12
 udowodnij szachownicę można pokryć tryminami  przyszly_naukowiec  1
 Szachownice - klasa abstrakcji  undothefuture  1
 rzut moneta na szachownice  wiedzma  1
 Czy na maturę przerobić w całości podręczniki z LO?  Jacus  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl