Zad. 1. W matematyce graf to zbiór punktów (wierzchołków), z których część została połączona krawędziami. Zazwyczaj przedstawia się go w formie diagramu (przykład na rysunku poniżej).
Aby informacje zawarte w grafie można było przetwarzać za pomocą komputera, musimy mieć inny (nierysunkowy) sposób przedstawienia grafu. Narysuj diagramy odpowiadające poniższym maszynowym reprezentacjom grafu (które są bardzo intuicyjne).
A) graphA = {1:[2, 3, 5], 2:[1, 3, 4], 3:[2, 4], 4: [1, 5]}
B) graphB = [('A', 'B'), ('A', 'C'), ('A', 'E'), ('B', 'A'), ('B', 'C'), ('B', 'E'),
('C', 'A'), ('C', 'C'), ('C', 'D'), ('D', 'A'), ('E', 'C')]
C) graphC = [
[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]
]
D) graphD = [
[0, 0, 12, 8, 4],
[6, 0, 16, 7, 5],
[13, 5, 0, 9, 0],
[0, 0, 22, 0, 0],
[21, 7, 5, 4, 0]
]
Zad. 2. Ile łez trzeba wypłakać, by zawarta w nich sól ważyła kilogram?
Zad. 3. Starożytne egipskie posągi faraonów mają zazwyczaj jedną stopę wysuniętą do przodu. Którą? Dlaczego? A co, jeśli nie mają?
W tym miesiącu punkty zdobyli:
- 3 - Krystyna Lisiowska - redaktor z Warszawy, Szymon Meyer - analityk danych z Dziewkowic, Tomasz Tomiczek - nauczyciel z Lipowej,
- 2,5 - Agata Centkowska - informatyk z Biela,
- 2 - Andrzej Piasecki - administrator IT z Oleśnicy.
Zad. 1. Połączenia w grafach zakodowane są w następujący sposób:
A) lista następników - dla każdego wierzchołka zawiera listę wierzchołków, z którymi jest on połączony.
B) lista krawędzi grafu,
C) macierz sąsiedztwa (zerojedynkowa) - kwadratowa macierz, w której jedynki wskazują, między którymi wierzchołkami grafu są połączenia,
D) macierz sąsiedztwa z wagami - kwadratowa macierz, w której liczby różne od zera wskazują, między którymi wierzchołkami grafu są połączenia i jakie mają one rangi (np. długości).
Ponieważ macierze w C i D nie są symetryczne względem przekątnej, muszą przedstawiać grafy skierowane.
Zad. 2. Zakładając, że łza waży 0,05 g i zawiera 1% soli, trzeba wylać 2 miliony łez, aby zawarta w nich sól ważyła 1 kg.
Zad. 3. Zazwyczaj wysunięta jest lewa noga - od strony serca, które jest siedzibą emocji, inteligencji i woli. Taki układ stóp oznaczał też odwagę (dlatego tradycyjnie wojsko zaczyna marsz lewa nogą). Oznacza to także, że przedstawiony na posągu faraon już nie żyje (wysunięta prawa noga oznacza, że posąg był postawiony za życia faraona). Nogi złączone przedstawione są zazwyczaj tylko u kobiet.
