---
title: MDL Lista 11
tags: MDL
author: Mateusz Reis
---
# MDL LISTA 11

## Zadanie 1
Załóżmy że mamy 4 wierzchołki w grafie oraz macierz sąsiedztwa

int matrix[4][4];

przykład :

$$
\begin{array}{c|lcr}
\frac{start}{end} & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 0 & 0 & 0\\
1 & 1 & 0 & 0 & 1\\
2 & 1 & 0 & 1 & 0\\
3 & 1 & 1 & 0 & 1\\
\end{array}
$$

gdzie indeks kolumny oznacza wierzchołek początkowy a indeks wiersza oznacza wierzchołek docelowy.

Aby wybrany wierzchołek był źródłem musimy sprawdzić czy ma krawędź prowadząca do wszystkich wierzchołków w grafie (kolumna n w każdym wierszu oprócz n ma 1) oraz czy nie ma krawędzi wchodzących (wiersz n ma same 0).
Możemy zrobić to w czasie liniowym po prostu przechodząc po każdym wierszu i kolumnie.

Algorytm działający w czasie liniowym:

const int n=4;
int matrix[n][n]={0,0,0,0,
                  1,0,0,1,
                  1,0,1,0,
                  1,1,0,1};

auto fun(auto idx)
{
    for(auto i=0;i<n;i++)
    {
        // dla matrix[n][n] musimy mieć 0 ponieważ krawędź z n do n
        // da nam łuk wchodzący 
        if(i!=idx)
        {
            //sprawdzamy czy istnieje krawędź wychodząca z idx do i
            // jeśli nie to idx nie jest źrodłem bo nie ma krawędzi 
            //łączącej go z i 
            if(!matrix[i][idx])
                return false;
        }
        //sprawdzamy krawędzie wchodzące jeśli istnieją to idx nie jest 
        //źródłem bo istnieje krawędź wchodząca 
        if(matrix[idx][i])
            return false;
    }
    return true;
}

## Zadanie 2
Aby posortować wierzchołki grafu możemy użyć DFS oraz listy, na początek której będziemy wstawiać odwiedzony wierzchołek po odwiedzeniu jego wszystkich sąsiadów.

Algorytm może wyglądać tak :

std::set<int> visited;
std::list<int> output;
//reprezentacja grafu za pomoca list sasiedztwa 
std::map<int,std::vector<int>> graph;

void DFS(auto idx)
{
    visited.insert(idx);
    for(auto &x:graph[idx])
        if(!visited.contains(x))DFS(x);
    output.push_front(idx);
}

auto sort()
{
    for(auto &i:graph)
        if(!visited.contains(i.first))DFS(i.first);
}

    

Przykład mamy graf skierowany (wierzchołki mają inne numery ale zaczniemy od tego z najmniejszym)


Algorytm wstawi wierzchołki w tej kolejności :

Ponieważ wstawia je na początek listy to lista wynikowa będzie wyglądać tak :

7,5,11,3,10,8,9,2

Każdy wierchołek odwiedzimy tylko raz idąc tylko raz każdą krawędzią wieć złożoność to O(n+m)

## Zadanie 3

Weźmy wierzchołek **u** o największym liczbie krawędzi wychodzących i oznaczmy ją jako |**S**| gdzie **S** to zbiór sąsiadów do których możemy się dostać bezpośrednio z **u**.

Jeśli |**S**| = |V|-1 to droga do każdego wierzchołka ma długość 1, więc znaleźliśmy pasujący wierzchołek.

Przykład :


Wierzchołek **1** ma same krawędzie wychodzące, więc możemy dostać się do każdego innego wierzchołka drogą o długości 1.

W p.p.
Wiemy że nasz wierzchołek ma |**S**| sąsiadów do których możemy się udać i |**P**|=|V|-|**S**| sąsiadów do których nie możemy sie udać z **u**, ale możemy dostać się do nich poprzez sąsiadów **s** należących do **S** i wtedy droga wynosi 2.
Aby to pokazać załóżmy niewprost, że istnieje taki wierzchołek **p** należący do **P** że nie istnieje do niego krawędź z **u** ani z dowolonego **s** należącego do **S**. Wtedy wszystkie krawędzie pomiędzy **p** oraz **s** i **u** są wychodzące z **p** czyli **p** ma |**S**| + 1 sąsiadów do których może się udać, co jest sprzeczne z założeniem bo wybieramy wierzchołek o największym |**S**|.

## Zadanie 6

Chcemy pokazać że każdy turniej posiada ścieżkę Hamiltona, aby to zrobić użyjemy indukcji po liczbie wierzchołków.

- Podstawa
- n = 1 w tym przypadku mamy tylko jeden wierzchołek więc ścieżka w oczywisty sposób istnieje


- n = 2 tutaj mamy jedną krawędź więc ścieżka Hamiltona istnieje


- Załóżmy że warunek zachodzi dla n i pokażmy dla n+1. W turnieju o n+1 wierzchołkach wybieramy jeden z nich i oznaczamy go jako **u** teraz dzielimy graf na 3 podgrafy A,B i **u**. A zawiera wierzchołki z których wychodzi krawędź do **u**, natomiast B zawiera wierzchołki do których istnieje krawędź z **u**. Wiemy że |A|<=n oraz |B|<=n więc dla obydwóch grafów z założenia mamy ścieżkę Hamiltona. Wystarczy że koniec ścieżki z A połączymy z **u** oraz **u** połączymy z początkiem ścieżki B.


## Zadanie 5

Chcemy sprawdzić czy w kostce 3x3x3 istnieje ścieżka Hamiltona zaczynająca się w dowolonym rogu i kończąca się w środku. Aby to sprawdzić pokolorujemy sąsiednie kostki 1x1x1 na przemian na niebieski i czerwony.


Jak widać każdy róg ma kolor czerwony a środkowa kostka niebieski. Mamy 27 wierzchołków i użyjemy 26 krawędzi aby odwiedzić je wszystkie, więc przy dowolnej ścieżce skończymy na kostce o kolorze czerwonym czyli nigdy nie skończymy ścieżki w środkowej kostce, ponieważ każda ścieżka o parzystej długości przy przechodzeniu za każdym razem na inny kolor zakończy się w tym samym kolorze.