Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Algorithm and program for finding minimal and quasi-minimal cuts in graphs

Tytuł:
Algorithm and program for finding minimal and quasi-minimal cuts in graphs
Algorytm i program znajdowania minimalnych i quasi-minimalnych przekrojów grafu
Autorzy:
Grishkeyich, A.
Piątek, Ł.
Powiązania:
https://bibliotekanauki.pl/articles/268053.pdf
Data publikacji:
2008
Wydawca:
Politechnika Gdańska. Wydział Elektrotechniki i Automatyki
Tematy:
krata dystrybutywna
przekrój nierozkladalny
jeden, dwu, trzy elementowy przekrój
distributive lattice
indecomposable cut
one-, two-, three- elements cut
Źródło:
Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej; 2008, 25; 49-52
1425-5766
2353-1290
Język:
angielski
Prawa:
Wszystkie prawa zastrzeżone. Swoboda użytkownika ograniczona do ustawowego zakresu dozwolonego użytku
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
It was found, that the set of minimum cuts, separating two chosen vertices in graph, have the structure of distributive lattice. It was developed an effective procedure for finding the set of 1, 2 and 3 elements cuts in graph based on the consideration of distributive lattice of the set of minimum cuts. The procedure consists of first, the algorithm for finding indecomposable minimal cuts of distributive lattice. Second, algorithm for synthesis, using resulting subset from stage one, of the entire set of minimum cuts. The third, is the algorithm for describing the set of quasi-minimum (close to the minimum, next to minimum) cuts in the form of sum of distributive lattices of minimal cuts found for the modified function of weight. The computer program, implementing these algorithms, is presented with examples.

Ustalono, że zbiór minimalnych przekrojów, rozdzielających dwa zadane wierzchołki grafu, z wprowadzonymi na i operacjami ma strukturę kraty dystrybutywnej. Opracowano skuteczną algorytmiczną procedurę znajdowania zbioru jed dwu i trzy elementowych przekrojów grafu bazującą na rozpatrzeniu dystrybutywnych krat zbioru minimalnych przekrojów grafu. Procedura składa się z, po pierwsze, algorytmu szukania nierozkładalnych minimalnych przekrojów Dystrybutywnej, po drugie, algorytmu syntezy po tym podzbiorze w kracie dystrybutywnej całego poszukiwanego zbioru minimalnych przekrojów i, po trzecie, algorytmu opisu zbioru quasi-minimalnych (bliskich do minimalnych, następnych po minimalnych) przekrojów w formie sumy krat dystrybutywnych minimalnych przekrojów, znalezionych dla zmodyfikowanej funkcji wagi. Przedstawiono zrealizowany program komputerowy i przedstawiono przykłady pracy programu.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies