Wpis z mikrobloga

@JakTamCoTam: Sam średnio wiem o co w tym chodzi. Nie no, tak mi się wydaje, że musisz sprawdzić czy da się połączyć wszystkie krawędzie w grafie w jakiś sposób. Spróbuj za k wziąć jakąś konkretną liczbę i się pobawić.
  • Odpowiedz
@D3xxT3r: Narysuj sobie graf z tymi osobami i zieloną krawędzią połącz te wierzchołki, które odpowiadają osobom, które się znają, a czerwoną krawędzią te, które się nie znają. Następnie wybierz osobnika i sprawdź, czy da się wybrać k zielonych krawędzi incydentnych z nim tak, żeby między wybranymi sąsiadami odpowiadającym drugim końcom krawędzi żaden się nie znał.
  • Odpowiedz
@kolnay1: ale tu nie chodzi o konkretny graf, jak rozumiem, tylko o dowiedzenie czy będzie możliwe takie dobranie osób przy dowolnym grafie i dowolnym k
  • Odpowiedz
jeśli k jest równe stopniowi jego wierzchołka w grafie to na pewno jest to możliwe, ale to dosyć oczywisty przypadek, a tak poza tym to nie wiem


@devs: Np. gdy każdy się zna to też jest to na pewno możliwe?
  • Odpowiedz
@kolnay1: nie, od razu zrozumiałem idiotyczność tego. Chodziło mi o to, że można zawsze stworzyć graf dla dowolnego k, przy którym będzie się dało to zrobić właśnie w ten sposób.
Zatem trzeba udowodnić, że da się to zrobić dla każdego innego grafu.
  • Odpowiedz
@devs: Przy dowolnym grafie i dowolnym k oczywiście nie wiadomo nic. Problem Casanovy sprowadza się do szukania zbioru niezależnego np. w sposób, który opisałem i jest NP-trudny.
  • Odpowiedz
@kolnay1: no, ale to nie jest odpowiedź na to pytanie z posta opa. To jest tylko algorytm, oczywisty zresztą, do rozwiązania określonego zadania tego typu.
  • Odpowiedz
@kolnay1: bardziej chodziłoby mi o pomoc przy rozwiązaniu ewentualnie jakieś źródło w necie, gdzie można to podejrzeć, bo ja kompletnie nie wiem jak to ruszyć ( ͡° ʖ̯ ͡°)
  • Odpowiedz