Jak wyznaczyć promień i średnicę grafu dwudzielnego graf: Jak wyznaczyć promień i średnicę grafu dwudzielnego (X_k, Y_k, E_k), gdzie: U_k = {1, 2, 3, ... } , gdzie k ≥ 5 X_k − składa się ze wszystkich 2−elem podzbiorów zbioru U_k Y_k − składa się ze wszystkich 3−elem podzbiorów zbioru U_k Krawędź istnieje ⇔ x jest podzbiorem y (x ∊ X_k, y ∊ Y_k) Narysowałem ten graf dla k = 5. Z każdego 2−elem zbioru wychodzą 3 krawędzie, do każdego 3−elem także dochodzą 3 krawędzie. Nie wiem jak z tego wywnioskować jaki jest promień i średnica grafu. Niestety, mam duży problem ze znajdywaniem średnicy i promienia grafu, więc jeśli ktoś byłby w stanie wytłumaczyć to na dowolnym przykładzie, będę bardzo wdzięczny.

Adamm: V_k = X_k ∪ Y_k promień = min_v∊Vk e(v) = min_v∊Vk max_u∊Vk d(v, u), gdzie d(v, u) to długość najmniejszej ścieżki łączącej v oraz u. średnica = max_{v, y∊Vk} d(v, u) Zauważ że dowolna bijekcja f:U_k → U_k definiuje nam automorfizm f' tego grafu, dany przez f'(v) = f(v), gdzie v∊V_k. Tzn. jeśli np. v = {x, y}, to f'(v) = {f(x), f(y)}. Automorfizmy te pokazują, że jeśli k≥6, to promień i średnica będzie taka sama, jak dla przypadku k = 6. Faktycznie, d(v, u) = d(v', u') gdzie v', u'⊆U₆. Zatem wystarczy rozpatrzeć dwa przypadki, k = 5 oraz k = 6.