  |
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
|
|
| ° Forum ° Odpowiedz ° Rejestracja ° Szukaj ° | |
| samochody ciężarowe ° Auto giełda ° Sprzedam motocykle ° |
 |
Matma / graf - połączenia |
| Autor | Wiadomo¶ć |
| Sliwtan
|
Posted: 14 Sty 2001 13:24:50 Witam Mamy graf złożony z wierzchołków białych i czarnych i pewnej liczby krawędzi, ale tylko łączących wierzchołki różnego koloru. Niech zbiór A będzie zbiorem krawędzi takim, że żadne dwie krawędzie nie są ze sobą połącznone, tj. nie mają wspólnego wierzchołka. Jam mam znaleźć maksymalną liczbę elementów zbioru A? Wydaje mi się, że będę musiał skorzystać z tablicy n x m, gdzie n to liczba wierchołków czarnych a m - białych, natomiast elementy tej tablicy to wartości logiczne odpowidające krawędzi lub braku krawędzi. TIA pzdr. Sliwtan |
| marcel
|
Posted: 11 Sty 2001 17:27:41 Jam mam znaleźć maksymalną
liczbę elementów zbioru A? Wydaje mi się, że będę musiał skorzystać z tablicy n x m, gdzie n to liczba wierchołków czarnych a m - białych, natomiast elementy tej tablicy to wartości logiczne odpowidające krawędzi lub braku krawędzi. masz znalezc maksymalne skojarzenie w grafie dwudzielnym :) najlatwiej zrobic to max przeplywem, tzn. utworzyc dwa nowe wierzcholki (zrodlo i ujscie), ze zrodla poprowadzic krawedzie do wszystkich czarnych, ze wszystkich bialych poprowadzic krawedzie do zrodla (wszystkie krawedzie traktujesz teraz jak skierowane - prowadza od czarnych do bialych) teraz algorytm wyglada nastepujaco - dopoki istnieje droga ze zrodla do ujscia, zwieksz A o 1 i odwroc krawedzie tej drogi |