[ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Grafy
PostNapisane: 9 wrz 2007, o 15: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
 Kolorowanie grafów - 3-krytyczne grafy
Wskaż wszystkie 3-krytyczne grafy (tzn. takie, które maja liczbe chromatyczna 3 i usuniecie dowolnego wierzchołka powoduje obnizenie liczby chromatycznej). Liczba chromatyczna grafu G, oznaczana przez \chi...
 flashion  0
 Grafy i drzewa matematyka dyskretna
WitaM wszystkich! Zwracam sie do Was z ogromną prośba! Profesor zawalił mnie zadaniami (15) i nie wiem jak sie zabrać za dwa z nich. Jeśli ktoś mógłby mi pomóc będę bardzo wdzięczny! Niżej podaje treść zadań: 1. Niech T będzie pełnym drzewem binarny...
 threetwos  1
 kombinatoryka, grafy - zadania
Witam, proszę o pomoc w rozwiązaniu paru zadań: 1) Mamy p kul białych i q kul czarnych, wkładamy je jedna za drugą. Ile jest sposobów takiego ułożenia jeżeli dwie kule czarne nie mogę leżeć obok siebie? 2) Należy zorganizować plan kontaktów w siadc...
 gelusia  3
 grafy eulerowskie i hamiltonowskie
Przedstaw cztery pięciowierzchołkowe grafy: a) niehamiltonowski i nieeulerowski, b) eulerowski i hamiltonowski, c) eulerowski, ale nie hamiltonowski, d) hamiltonowski, ale nie eulerowski....
 kasienkaj91  20
 grafy-zachłanny algorytm kolorowania
zad.1 Uporządkujmy wierzchołki grafu G w taki sposób, że d(x_1)\geq d(x_2)\geq \ldots \geq d(x_n). Pokazać, że przy takim uporządkowaniu wierzchołków, zachłanny algoryt...
 borubarek  2
 grafy, zależności
Niech G = (V, E) będzie takim grafem, że |V | = 2m dla pewnego m \ge ­2 oraz G nie zawiera K3 jako podgrafu. Pokazać, że [tex:...
 Edi___89  0
 grafy planarne - zadanie 3
witam, mam pytanie (może i głupie), co oznacza sformułowanie, że dany graf jest bez 4-cykli? czy tzn,że dany graf nie ma cykli długości 4, czy może że ten graf ma mniej niż 4 cykle? proszę o odpowiedź...
 dela  2
 Logika, grafy, tozsamosci: kolokwium
Czy potrafilibyście rozwiązać i wyjaśnić poszególne zadania? 1. Okresl wartosc logiczna (Prawda, Fałsz, Nie wiadomo) zdan: W TYM ZADANIU PODAJESZ TYLKO ODPOWIEDZI! a) Kazde drzewo o 11 krawedziach ma 12 wierzchołków; b) Kazde drzewo jest grafem dwud...
 mmsmm  4
 Grafy Eulera
Witam. Prosiłbym o pomoc w następujących zadaniach: Zadanie 1. Czy istnieje graf Eulera z parzystą liczbą wierzchołków i nieparzystą liczbą krawędzi? Jeżeli tak to podaj przykład, jeżeli nie to udowodnij. Zadanie 2. Niech L(G&#4...
 Summum Malum  3
 Grafy cykle nieparzyste
Jak udowodnić: Jeśli graf nie zawiera cykli nieparzystych to jest dwudzielny?...
 mike_btls  2
 Grafy - dwa zadania
(a) Udowodnij, że graf niezorientowany jest drzewem wtedy i tylko wtedy, gdy dowolne dwa różne wierzchołki są połączone dokładnie jedną drogą, której wszystkie wierzchołki są różne. (b) Załóżmy, że Twoim zadaniem jest zorganizowanie wystawy. Jed...
 fcluki07  1
 cykle hamiltona - grafy dwudzielne-problem nadal aktualny
Czy ktos mógłby podać rozwiazanie wraz z odopwiedzia jak do tego doszedł do zadania: a)Ile cykli Hamiltona ma graf K_{n,n}dla n \geqslant2 b)Ile jest dróg Hamiltona w grafie K_...
 mateuss  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com