Wszystko

Wszystkie

Archiwum

tjmps
tjmps
  • 0
@konik_polanowy: To ciekawe zagadnienie. Wszystko się łączy z wszystkim. Napisz po przeczytaniu Kolego jakiś ciekawy program dla amatorów. Taki prosty ale z kawałkiem teorii. Może jeszcze zdążę o tym opowiedzieć uczniom (gimnazjum).
  • Odpowiedz
Blomex
Blomex
  • 1
@Zgredzimierz: no to sobie rysujesz, graf regularny nie musi być spójny, więc żeby wszystkie były stopnia 1 to po prostu rysujesz krawędź między wierzchołkami z których jeszcze nie wychodzi żadna krawędź. (spoiler na wikipedii: https://pl.wikipedia.org/wiki/Graf_regularny ). A graf o wszystkich wierzchołkach stopnia 2 to np jeden cykl. ze stopniem 4 trzeba chwilę pomyśleć ale powinno wyjść rysując "na pałę" (zauważ, że ten sam trick co przy zwiększaniu stopnia o 1 zadziała
  • Odpowiedz
Blomex
Blomex
  • 1
@wamaga: można też indukcyjnie: zaczynamy od trójkąta i w każdym kroku robimy:
(Algorytm:)
1. Wybieramy dowolny trójkąt z istniejących
2. Rysujemy wierzcholek w jego srodku i 3 krawędzie
3. Powstają 3 trójkąty zamiast 1, liczba wierzchołków zwiększa się o 1, ścian o 2, krawędzi o 3 więc wzóe eulera działa. Tak utworzony graf nadal jest planarny.
Z założenia indukcyjnego m=3n-6 (dziala dla trójkąta 3=3) po zwiększeniu liczby wierzchołków o 1 i
  • Odpowiedz
tell_me_more
tell_me_more
  • 2
@TenAnonToKlopoty:

std::map< std::pair, bool > edges;

Dodawanie, usuwanie krawędzi O(1), dodawanie wierzchołków O(1), jedynie usuwanie wierzchołków O(liczba wierzchołków). Można przyśpieszyć dodając listę sąsiedztwa:

std::map< int, std::set > neighbors;
  • Odpowiedz
kolnay1
kolnay1
  • 1
#matematyka #grafy
We wprowadzeniu do teorii grafów Wilsona jest takie zadanie:

26.3s Let E be the set of letters in the word MATROIDS. Show that the family (STAR, ROAD, MOAT, RIOT, RIDS, DAMS, MIST) of subsets of E has exactly eight transversal.

Wie ktoś jak to się sprytnie robi? Tutaj transwersalem będzie siedmioliterowy wyraz, o pierwszej literze z pierwszego słowa z rodziny, drugiej z drugiego, itd, gdzie żadna litera się nie powtarza,
miszczu90
miszczu90
  • 0
@bialy100k: No to na logikę, oczywiście wykorzystać grafy, 0- oblewane poklei, następna kolejka wokół 1 - też następne - tak jak na obrazku, i sprawdzanie i w pętli 0-15 ifką i niech sam sprawdza co mu najbardziej się opłaca. Nie wiem tylko ile trzeba zmiennych do tego - chyba 3 bieżąca, datą najbardziej opłacalna i licznikowa.
  • Odpowiedz
bialy100k
bialy100k
  • 0
@miszczu90:
@destruktiw_kommandoh:

Wczoraj razie próbowałem właśnie metody zbliżonej do @miszczu90 - ale "na piechotę".
Czyli oblewanie po kolei eliminując istniejące "duplikaty" ( Na rysunku "wiodący" kolor ma cyferki czerwone/żółte). Po tej operacji mam zestaw obiektów które muszę że tak powiem "uprościć", czyli to, co się da wpasować w już istniejące miejsca. Jednak nie mam faktycznie dobrej metody na to "upraszczanie". Wiadomo, że trzeba znaleźć i "nałożyć" maksymalnie dużą liczbę kolorów.
bialy100k - @miszczu90: @destruktiw_kommandoh: Wczoraj razie próbowałem właśnie m...

źródło: comment_WFH0LnLslGX4CamjJPohEyzk4XkQTgkS.jpg

Pobierz
  • Odpowiedz

Powiązane tagi