szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Grafy
PostNapisane: 9 wrz 2007, o 14:54 
Użytkownik

Posty: 19
Lokalizacja: Białystok
1)Kazda sciane szescianu dzielimy nan^{2} przystajacych kwadratów. Wierzcholkami grafu G sa wierzcholki wszystkich tych kwadratów, a krawedziami wszystkie ich krawedzie. Ile krawedzi i
wierzcholków ma ten graf? Czy jest to graf planarny?
-|E|=2(n+1)n-6n, |V|=(n+1)^2-6(n+1)-6 :?:

2)Niech G = (V, E) bedzie takim grafem, ze | V | > 4 oraz dla dowolnych trzech wierzcholków
u, v i w co najmniej dwie sposród krawedzi { u, v } , { u, w } , { v, w } naleza do E. Udowodnic, ze
G jest hamiltonowski.

3)Ile isnieje nieizomorficznych drzew spinajacych graf osmioscianu foremnego? Ile jest wszys-
tkich drzew spinajacych graf osmioscianu foremnego o ponumerowanych wierzcholkach?

4)Ile jest nieizomorficznych drzew o 14 wierzcholkach, których stopnie s� równe 1 lub 3. Czy
istnieje takie drzewo o 13 wierzcholkach?

5)Czy grafy stopnia 4 bez cykli dlugosci 3 sa planarne?

6)Udowodnic, ze krawedzie dowolnego hamiltonowskiego grafu regularnego stopnia 3 mozna
pomalowac trzema kolorami tak, zeby krawedzie maj�ace wspólny wierzcholek byly róznej barwy.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Grafy - zadanie 2
Będę niezmiernie wdzięczna za pomoc w zrobieniu tego zadanka Niech G będzie grafem prostym, nieskierowanym, w którym połączenia między w...
 blanka_00  1
 grafy - zadanie 4
Niech G* będzie grafem, którego zbiorem wierzchołków są krawędzie danego grafu niezorientowanego G, natomiast krawędzie łączą tylko te wierzchołki w grafie G*, które odpowiadają krawędziom sąsiednim w grafie G. Graf G* nazywamy grafem dualnym grafu G...
 kubawymiatacz  0
 Grafy - zadanie 3
Hej! Możecie mi pomóc z zadaniami? 1. W grafie prostym G = dla każdej nie połączonej pary wierzchołków x i y zachodzi deg(x)+deg&#40...
 dusia17  0
 [grafy]Las, którego dopełnienie jest drzewem.
Szanowni Państwo, mam problem z pewnym zadaniem. Pytanie brzmi: Na ilu wierzchołkach można zbudować las, którego dopełnienie jest drzewem? Doszedłem do tego, że dla <5 wierzchołków jest to możliwe. Dlaczego tak jest? Z czego to wynika? Z góry d...
 hoot1hooten  1
 Grafy-liczba chromatyczna, dopełnienia i dwudzielność
1) Udowodnij, że: \chi (G) \cdot \chi (G') \le \frac{1}{4} (n+1)^{2} G' - dopełnienie grafu G \left|V(G&#4...
 miodzio1988  7
 Kilka pytań o grafy
Witam, poniżej co do których swoich odpowiuedzi nie jestem pewien. Bardzo proszę o sprawdzenie. Może być 0,1,2,3 poprawnych odpowiedzi 1) Graf pełny G = (V,E) gdzie |V|=9 jest grafem ...
 Fixus  8
 Grafy dwudzielne
1.Narysuj graf dwudzielny G reprezętujący następujace relacje:''x jest dzielnikiem y" gdzie x\in \left\{ 2,3,5,7,11\} y\in\left\{ 99,110,111,112\} W grafie G znaleźć wszystkie skojarzenia maksymalne. 2.Załóżmy, że...
 dyziu  0
 Spójność i grafy dwudzielne
Pokazać,że jeśli \delta \ge n-2 to \kappa(G)=n-2 . Proszę o jakąś wskazówkę...
 gardner  3
 grafy - drzewo
Hej! Ma ktoś pomysł na zadania: 1. W drzewie T przez w_k oznaczamy liczbę wierzchołków stopnia k=1,2,... Mamy drzewo, w którym w_2+w_3+w_4+w_5=12[...
 dusia17  0
 Wszystkie grafy nieplanarne o 6 wierzchołkach
Znajdź wszystkie grafy o 6 wierzchołkach, których nie da się narysować na płaszczyźnie bez przecinania się krawędzi (nie są planarne). Czy odpowiedzią jest 11? Skorzystałem z twierdzenia Kuratowskiego: Graf K_{3,3} oraz ...
 donmaciej  2
 Dowody i uzasadnienia - Grafy
a) Udowodnić że suma stopni wierzchołków dowolnego grafu spójnego jest dwa razy większa od liczby jego wierzchołków b) Uzasadnić, że w grafie pełnym o n wierzchołkach istnieje droga Hamiltona, a następnie wyznaczyć liczbę takich dróg c) Podać przykła...
 laki_me  8
 Grafy - skladowe spojne
Sprawdzić, czy graf o 8 wierzchołkach i 16 krawędziach może posiadać więcej niż 2 składowepro spójne. Na początku ten problem próbował rozwiązać w ten sposób \begin{cases} 8-k>16 \\ \frac{(8-k)(7-k)}{2} \end{cases}...
 fxBobi  2
 Grafy - mapy - algorytm
Witam Potrzebuję napisać algorytm do sprawdzenia czy dany graf jest mapą. Przydałoby mi się kilka własności map grafowych. Niestety google niezbyt konkretnie odpowiada na moje zapytania. Dlatego pytam Was, jakie własności ma mapa, najlepiej żeby był...
 Tosny  0
 liczba chromatyczna - grafy
Wykaż, że \chi(G)+\chi(\overline{G})\geq 2\sqrt{n} ...
 borubarek  0
 grafy, sieci
Podać przykład sieci, w której istnieją dwa różne przekroje minimalne...
 Edi___89  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com