spójność krawędziowa a stopień wierzchołka
-
- Użytkownik
- Posty: 487
- Rejestracja: 1 lis 2012, o 20:56
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 226 razy
spójność krawędziowa a stopień wierzchołka
W grafie G zachodzi nierówność:
\(\displaystyle{ \lambda \left( G\right) \le \delta \left( G\right)}\)
\(\displaystyle{ \lambda \left( G\right)}\)-spójność krawędziowa
\(\displaystyle{ \delta \left( G\right)}\)-minimalny stopień
Jak udowodnić taką nierówność ? Proszę o pomoc
\(\displaystyle{ \lambda \left( G\right) \le \delta \left( G\right)}\)
\(\displaystyle{ \lambda \left( G\right)}\)-spójność krawędziowa
\(\displaystyle{ \delta \left( G\right)}\)-minimalny stopień
Jak udowodnić taką nierówność ? Proszę o pomoc
-
- Użytkownik
- Posty: 61
- Rejestracja: 31 sie 2013, o 00:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 25 razy
spójność krawędziowa a stopień wierzchołka
Rozważ wierzchołek o minimalnym stopniu \(\displaystyle{ \delta(G)}\) i usuń z grafu wszystkie krawędzie z niego wychodzące. Graf z pewnością stanie się niespójny, co więc to oznacza dla \(\displaystyle{ \lambda(G)}\)?
-
- Użytkownik
- Posty: 487
- Rejestracja: 1 lis 2012, o 20:56
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 226 razy
spójność krawędziowa a stopień wierzchołka
Jakoś tego nie widzę. Jeżeli usunę wszystkie krawędzie z wierzchołka, to ten wierzchołek będzie wierzchołkiem izolowanym. A co z tego wynika nie wiem ?
-
- Użytkownik
- Posty: 61
- Rejestracja: 31 sie 2013, o 00:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 25 razy
spójność krawędziowa a stopień wierzchołka
Po usunięciu \(\displaystyle{ \delta(G)}\) krawędzi graf przestaje być spójny. A jak definiuje się liczbę \(\displaystyle{ \lambda(G)}\)?
-
- Użytkownik
- Posty: 487
- Rejestracja: 1 lis 2012, o 20:56
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 226 razy
spójność krawędziowa a stopień wierzchołka
Znam dwie definicję.thom pisze:Po usunięciu \(\displaystyle{ \delta(G)}\) krawędzi graf przestaje być spójny. A jak definiuje się liczbę \(\displaystyle{ \lambda(G)}\)?
Najmniejsza liczba krawędzi, którą należy usnąć aby graf przestał być spójny.
Liczba krawędzi należących do najmniej licznego rozcięcia grafu.
Czyli , liczba krawędzi wynosi \(\displaystyle{ 0}\)w najmniej licznym rozcięciu , a stopień wierzchołka również \(\displaystyle{ 0}\) czyli nierówność jest spełniona ?
-
- Użytkownik
- Posty: 61
- Rejestracja: 31 sie 2013, o 00:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 25 razy
spójność krawędziowa a stopień wierzchołka
Zatem \(\displaystyle{ \lambda(G)\leq\delta(G)}\).Najmniejsza liczba krawędzi, którą należy usnąć aby graf przestał być spójny.
-
- Użytkownik
- Posty: 487
- Rejestracja: 1 lis 2012, o 20:56
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 226 razy
spójność krawędziowa a stopień wierzchołka
No właśnie dlaczego zatem ? Z czego to wynika ? Nie mogę się połapaćthom pisze:Zatem \(\displaystyle{ \lambda(G)\leq\delta(G)}\).Najmniejsza liczba krawędzi, którą należy usnąć aby graf przestał być spójny.
-
- Użytkownik
- Posty: 61
- Rejestracja: 31 sie 2013, o 00:27
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 25 razy
spójność krawędziowa a stopień wierzchołka
Wystarczy usunąć \(\displaystyle{ \delta(G)}\) krawędzi, aby graf nie był spójny, podczas gdy \(\displaystyle{ \lambda(G)}\) jest minimalną liczbą krawędzi potrzebną do uzyskania tego efektu.
-
- Użytkownik
- Posty: 487
- Rejestracja: 1 lis 2012, o 20:56
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 226 razy