Teoria grafów - ile maksymalnie dużych miast posiada państwo? ko: W państwie Antagola każde duże miasto jest połączone linią lotniczą z dokładnie trzema innymi dużymi miastami Antagolii. Poza ˙ tym, z każdego dużego miasta można dolecieć do dowolnego dużego miasta z najwyżej jedną przesiadką. Ile maksymalnie dużych miast posiada Antagola? Dlaczego?

wredulus_pospolitus: 1) Z każdego do każdego miasta można dolecieć z maksymalnie jedną przesiadką, to miast na pewno nie może być więcej niż ... 13. Dlaczego? Ponieważ: Wylatujemy z miasta (1). Możemy dolecieć do miast (2), (3), (4). Z każdego z tych miast możemy dolecieć do trzy INNYCH miast (czyli miasta od (5) do właśnie (13)). Jednak czy to jest prawidłowa odpowiedź? Czy przy 13 miastach można zrobić taką siatkę, aby z KAŻDEGO miasta można było się dostać do każdego miasta Zastanów się chwilę nad tym problemem i nanieś odpowiednie poprawki.

kerajs: nie ma sensu zastanawiać się nad 13 miastami skoro z każdego z miast (2), (3), (4) można dolecieć do (1) i dwóch innych miast.

Blee: Warto, gdyż w tym momencie już mamy szacowanie górne z głowy więc mocno przybliżamy się do rozwiązania.

kerajs:

	3*13
Ponadto dla 13 miast graf miałby		=.... krawędzi.
	2

Mikrożmirłacz.

kerajs:

	3*13
Ponadto dla 13 miast graf miałby		=.... krawędzi.
	2

Mikrożmirłacz.

kerajs: @Blee Nie masz pojęcia o czym piszesz. Gdyby Wredulus się nie pomylił, to miałby poprawne ograniczenie z góry.

Blee: Blee i werdulus to jedna i ta sama osoba Druga sprawa − ograniczenie górne 13 miast zostało przeprowadzone zanim w ogóle się siadło do zadania i patrzyło na teorie grafów. Było to PIERWSZE ograniczenie i w trakcie pisania o nim napisałem, że autor musi nanieś POPRAWKI (czyli mocniej ograniczyć)

kerajs: No to pokażę gdzie się pomyliłeś: Napisałeś: '' Z każdego do każdego miasta można dolecieć z maksymalnie jedną przesiadką, to miast na pewno nie może być więcej niż ... 13. Dlaczego? Ponieważ: Wylatujemy z miasta (1). Możemy dolecieć do miast (2), (3), (4). Z każdego z tych miast możemy dolecieć do trzy INNYCH miast (czyli miasta od (5) do właśnie (13)).'' Zamiast: '' Z każdego do każdego miasta można dolecieć z maksymalnie jedną przesiadką, to miast na pewno nie może być więcej niż ... 10. Dlaczego? Ponieważ: Wylatujemy z miasta (1). Możemy dolecieć do miast (2), (3), (4). Z każdego z tych miast możemy dolecieć do (1) i dwóch INNYCH miast (czyli miasta od (5) do właśnie (10)).' Hint: Antagola może mieć 4,6,8 lub 10 miast.

student:

wredulus_pospolitus: @Student −−− lewy dolny skrajny nie dotrze do prawego górnego @kerajs −−− masz rację, za szybko oszacowałem z góry. 4 miasta − szybko można obalić

kerajs: Dla 10 dużych miast szukanym grafem jest najmniejszy żmirłacz, czyli graf ..... .