szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 lip 2015, o 17:33 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
1.1. W każdym grafie liczba wierzchołków stopni nieparzystych jest parzysta.
\sum_{}^{} degv=2\left| E\right|
\sum_{st.wierzcholkow parzystych}^{} +  \sum_{st.wierzcholkow nieparzystych}^{} = parzysta
Z tego wynika,że suma wierzchołków nieparzystych musi być parzysta.

1.2. Jeśli stopień każdego wierzchołka grafu G jest większy lub równy 2 to każdy wierzchołek
leży na pewnym cyklu prostym.

Tu nie bardzo wiedziałem jak się zabrać.

1.4. W każdym grafie G istnieje droga prosta długości co najmniej najmniejszego stopnia wierzchołka grafu.
Tu mam kontrprzykład :K_{3}

1.5. Jeśli G jest samo dopełniający się to reszta z dzielenia przez 4 liczby wierzchołków wynosi 0 lub 1
Liczba krawędzi grafu samo dopełniającego się jest połową krawędzi jaka występuje w grafie pełnym. Mamy więc,że \left| E\right|= \frac{n(n-1)}{4} Z tego wynika,że musi przystawać modulo 4 do 0 lub 1.

1.6. Jeśli najmniejszy stopień wierzchołka w grafie G wynosi co najmniej 2 to w G istnieje cykl.
Tutaj chyba trzeba wziąć najdłuższą drogę w naszym grafie. Jeżeli rozpatrzymy pierwszy wierzchołek naszej drogi to musi on mieć więc 2 sąsiadów. Jeden z nich oczywiście należy do naszej drogi a drugi:
jeśli nie należy do drogi to znajdziemy drogę dłuższą ,więc sprzeczność. Jeśli nie,to musi należeć do drogi,więc powstaje nam cykl (oczywiste po narysowaniu rysunku)
1.7. Podać nieskończenie wiele grafów G takich, że G jest izomorficzny ze swoim dopełnieniem.
Tutaj nie miałem pomysłu jak ruszyć.
1.8. Scharakteryzować grafy G takie, że każdy indukowany podgraf G jest spójny.
Czy odpowiedzią są wszystkie grafy pełne?
1.10. W każdym k-regularnym grafie istnieje 1/2 k rozłącznych krawędzi.
Tutaj nie wiedziałem jak przeprowadzić w miarę rozsądnie dowód. Proszę o wskazówki i sugestie.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 24 lip 2015, o 18:43 
Użytkownik

Posty: 59
Lokalizacja: Polska
Ad. 1.4: Chyba nie. Znajdziesz drogę długości 2 w trójkącie, czyż nie?
Góra
Mężczyzna Offline
PostNapisane: 4 sie 2015, o 20:21 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
1.2. Jeżeli przez cykl prosty rozumiesz cykl w którym wierzchołki się nie powtarzają to to nie jest prawda i łatwo podać kontrprzykład.
Góra
Mężczyzna Offline
PostNapisane: 6 sie 2015, o 22:46 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Mógłbyś go podać? Porysowałem trochę ale zawsze znajduję jakiś cykl prosty :(
Góra
Mężczyzna Offline
PostNapisane: 6 sie 2015, o 23:06 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
Oto przykład. Jak dla mnie "środkowy" wierzchołek nie leży na żadnym cyklu prostym
\begin{tikzpicture}
\draw (2,0)--(1,1)--(0,0)--(1,-1)--(2,0)--(3,0.5)--(4,0)--(5,1)--(6,0)--(5,-1)--(4,0)
\end{tikzpicture}
Góra
Mężczyzna Offline
PostNapisane: 6 sie 2015, o 23:23 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Nie wiem dlaczego ale sprawdzałem tylko grafy regularne.Dzięki wielkie ;)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 dziwne zadanie z matematyki dyskretnej  mkarwin  1
 takze dziwne zadanie z matematyki dyskretnej  mkarwin  5
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl