Wszystko

Wszystkie

Archiwum

Szarlej47
Szarlej47
  • 2
#matematyka #grafy #programowanie #informatyka
Jakie jest zastosowanie dla dominowania w grafach zewnętrznie planarnych?
Nie mogę nigdzie tego znaleźć w internetach. Jedyne co znalazłem to, że są przydatne przy rozwiązywaniu problemu galerii sztuki, a potrzebuję tego trochę więcej.
  • 1
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
Szarlej47
Szarlej47
  • 2
#matematyka #grafy #programowanie #informatyka
Jakie jest zastosowanie dla dominowania w grafach zewnętrznie planarnych?
Nie mogę nigdzie tego znaleźć w internetach. Jedyne co znalazłem to, że są przydatne przy rozwiązywaniu problemu galerii sztuki, a potrzebuję tego trochę więcej.
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
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
  • 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
  • Odpowiedz
T.....y
T.....y
  • 2
Jaka jest najlepsza implementacja grafu, jeżeli mam zamiar w nim zarówno dodawać jak i usuwać wierzchołki oraz krawędzie? Nie chcę również, żeby to były stałe tablice i wolałbym uniknąć tablicy sąsiedztwa na rzecz listy sąsiedztwa, bo grafy będą duże. #grafy #programowanie #algorytmy
  • 20
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
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
  • 1
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
bialy100k
bialy100k
  • 2
Zagadka:
Jakiej metody/strategii użyć kolorując plaster miodu 16 kolorami tak, by używając najmniejszej liczby pól każdy kolor sąsiadował z każdym. Ostatni kolor może być białym - czyli tłem i stykać się z innymi "jak woda" olewająca wyspę - ale może też być "jeziorem" jeżeli ktoś uzna za stosowne.

#grafy #matematyka #zagadka
bialy100k - Zagadka: Jakiej metody/strategii użyć kolorując plaster miodu 16 koloram...

źródło: comment_LWNl7O569QqCinZrcIpHnvohTHNLpvne.jpg

Pobierz
  • 4
  • Odpowiedz

  • Otrzymuj powiadomienia
    o nowych komentarzach
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
bialy100k - @miszczu90: @destruktiw_kommandoh: Wczoraj razie próbowałem właśnie m...

źródło: comment_WFH0LnLslGX4CamjJPohEyzk4XkQTgkS.jpg

Pobierz
  • Odpowiedz

Powiązane tagi