Delta mi!

Spójrzmy na dwa grafy na poniższym rysunku. Wyglądają zupełnie inaczej, prawda?

Zacznijmy od następującego zadania: dwunastu Indian (dla ustalenia uwagi i zgrabności tytułu przyjmijmy, że pochodzą oni z plemienia Mohikanów) siedzi dookoła ogniska i pali fajkę pokoju. Procedura rozpoczyna się rzecz jasna od Wodza, który po zapaleniu rzuca zdobytą od bladych twarzy symetryczną monetą i w zależności od wyniku podaje fajkę na lewo albo na prawo. Kolejny Indianin robi to samo - pali faję, rzuca monetą i podaje dalej (fajkę, nie monetę). Nietrudno uwierzyć, że prędzej czy później fajka wpadnie w ręce ostatniego Indianina, który jej wcześniej nie palił (będzie to tytułowy ostatni Mohikanin)...

Drodzy Poszukiwacze Przygód, witam Was na kolejnym szkoleniu. Dzisiaj nauczymy się jak rozpoznawać, znajdować i radzić sobie w boju z Hydrą. Hydry to paskudne stworzenia, zamieszkujące świat grafów. Niech Was nie zmyli rysunek obok. Zobaczcie, jak przerażająco on wygląda. Hydry to bestie, które tylko upodobniają się do drzew, aby Was zmylić! Tam, gdzie niektórzy z Was dostrzegają korzeń, znajduje się tułów bestii. Tam, gdzie wydają się być liście, są głowy naszego stwora. Krawędzie to szyje, a wierzchołki wewnętrzne to zgięcia.

W tym artykule zmierzymy się z problemem pokrycia wierzchołkowego (Vertex Cover). Poruszymy kilka kwestii na pograniczu optymalizacji liniowej, złożoności obliczeniowej oraz algorytmów parametryzowanych...

Które z rysunków 1 (a), (b), (c) da się narysować bez odrywania ołówka od kartki i bez rysowania ponownie wzdłuż narysowanej już linii?

Wojtek leżał na podłodze i czytał właśnie książkę o grafach, którą wypożyczył z biblioteki. Alicja, jego młodsza siostra, która przeglądała w tym czasie portal społecznościowy, spytała nagle...

Mimo licznych działań skierowanych na zwalczanie terroryzmu wiele organizacji terrorystycznych wciąż się powiększa. Aby poradzić sobie z tym problemem, agencje bezpieczeństwa poszukują nowych sposobów analizy pozwalających lepiej zrozumieć strukturę tych organizacji. Jednym z problemów jest zidentyfikowanie kluczowych członków organizacji terrorystycznej przy użyciu informacji jedynie o tym, jak wygląda sieć terrorystyczna - dzięki temu agencje bezpieczeństwa mogłyby skupić swoje ograniczone zasoby na tych jednostkach. W tym artykule omówimy nowe podejście do tego problemu oparte na teorii gier.

Znana łamigłówka wieże Hanoi ma następujące reguły...

Zadanie 44 w książce 100 zadań Hugona Steinhausa dotyczy zamkniętych dróg po krawędziach wielościanu foremnego, które przechodzą dokładnie jeden raz przez każdy wierzchołek, czyli złożonych z krawędzi cykli Hamiltona. Chodzi o to, aby znaleźć wszystkie kształty takich cykli i policzyć, ile ich jest (z dokładnością do położenia) dla każdego wielościanu foremnego.

Podczas XXVII Kongresu Matematycznego, odbywającego się w Seulu między 13 a 21 sierpnia 2014 roku, prestiżową Nagrodę Nevanlinny (informatyczny odpowiednik Medalu Fieldsa) otrzymał pracujący w USA hinduski informatyk Subhash Khot. W laudacji poświęconej wynikom Khota jego mentor i współautor wielu prac, Sanjeev Arora, wspomniał o przełomowym wyniku uzyskanym przez profesora Uniwersytetu Warszawskiego, Krzysztofa Oleszkiewicza wraz z Elchananem Mosselem i Ryanem O'Donnellem...

Teoria grafów to gałąź matematyki, do której powstania impuls dało liczące sobie już ćwierć tysiąclecia słynne zagadnienie mostów królewieckich, rozwiązane przez Leonharda Eulera. Osobiście lubię patrzeć na matematykę nie tylko jako na zbiór problemów ciekawych samych w sobie, ale również jak na model rzeczywistości, narzędzie pozwalające efektywniej radzić sobie z rzeczywistymi zmartwieniami. Obecnie teoria grafów staje się jednym z najpopularniejszych takich narzędzi, używanym chętnie przez matematyków (na rzecz innych gałęzi tej nauki), informatyków, fizyków, chemików, a nawet socjologów. Niniejszy artykuł ma na celu przedstawienie tego, jak zagadnienie kolorowania grafów służyć może za narzędzie przydatne w przydzielaniu częstotliwości nadajnikom w jednym z modeli sieci radiowej.

Zajmijmy się następującym klasycznym zadaniem: należy pokryć kwadrat jednostkowy kwadratowymi kafelkami o różnych bokach tak, aby żadne dwa kafelki nie nachodziły na siebie. Czytelnik może spróbować poszukać takiego kafelkowania metodą prób i błędów, ale na pierwszy rzut oka nie jest jasne, czy pokrycie o żądanych własnościach w ogóle istnieje...

Wśród wielu typów zagadnień matematycznych bardzo sobie cenię takie, które po wierzchu są elementarne, łatwe na początku i dające się rozwiązać nietypowymi, efektownymi, niecodziennymi metodami. Dobrze jest też, gdy zadania te są wierzchołkiem pewnej góry lodowej, albo – stosując inne porównanie – są początkiem ścieżki wiodącej nas w nieznane.

Pewnie część czytelników Delty zna grę Nim – zarówno jej zasady, jak i właściwą dla niej strategię wygrywającą. W tym artykule chcemy przedstawić inną grę grafową. Grę o prostych zasadach, ale trudniejszą niż Nim do dokładnego przeanalizowania. Tą grą jest – stworzony przez Jamie Peabody i Karen Willis – Grim. Podamy efektywny sposób orzekania, który gracz ma strategię wygrywającą. Co najciekawsze, można go zastosować do szerokiej klasy tego typu gier dwuosobowych, zawierającej Grima i Nima.

Skoro dotychczas szło nam tak dobrze, spróbujmy pójść za ciosem i zaproponować bardzo oszczędną reprezentację drzew już niekoniecznie binarnych (ale wciąż ukorzenionych)...

Wiele struktur danych w komputerze można reprezentować w postaci drzewa binarnego. Aby przechować takie drzewo w pamięci komputera, należy dla każdego węzła zapamiętać numer jego lewego i prawego syna oraz, jeśli to potrzebne, numer węzła będącego jego ojcem. Wystarczą nam do tego trzy tablice.

Przedstawimy tu dwa zagadnienia, w których pojawia się problem znajdowania najliczniejszego skojarzenia w grafie dwudzielnym, jednak trochę ukryty.

Cztery parametry. Tym, co najczęściej robi się w grafach dwudzielnych, jest znajdowanie najliczniejszego skojarzenia. Można jednak rozważać aż cztery – parami dualne – parametry powiązane z najliczniejszym skojarzeniem...

Ten numer Delty jest zdominowany przez tematykę skojarzeń w grafach. Dla przypomnienia: graf nieskierowany to zbiór wierzchołków połączonych krawędziami, skojarzenie zaś w tym grafie to taki podzbiór krawędzi  że każdy wierzchołek grafu jest incydentny z co najwyżej jedną krawędzią z 

Kiedy wędrujemy po pustyni i poczujemy zmęczenie, poszukujemy najbliższej oazy, w której moglibyśmy zregenerować siły. Jeśli mamy szczęście, możemy spotkać na pustyni beduina, który wskaże nam właściwy kierunek do oazy. Czy rzeczywiście właściwy?