szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Rysowanie grafu
PostNapisane: 22 lis 2010, o 20:19 
Użytkownik

Posty: 392
Mam narysowac graf nieskierowany. Nie moga wystepowac petle. Mam podany stopien kazdego wierzcholka i musze go narysowac. WIem ze sa warunki ze ilosc wierzch o nieparzystym stopniu musi byc parzysta oraz ze stopien maksymalny wierzcholka musi byc o 1 mniejszy od ilosci wierzcholkow. Sa moze jeszcze jakies warunki ? Jak narysowac taki graf? Czasami troche ciezko to narysowac;)
np. 1,2,3,3,3,4,4 nie umiem
Góra
Mężczyzna Offline
 Tytuł: Rysowanie grafu
PostNapisane: 22 lis 2010, o 22:58 
Użytkownik

Posty: 520
Lokalizacja: Warszawa
Np. graf V=\{a,b,c,d,e,f,g\}, E=\{ab, ac, ad, ae, cd, de, cf, ef, fg, ge\}. Jak otrzymałem ten graf? Wybrałem sobie wierzchołek o stopniu cztery(pisze sobie przy nim 4 by o tym cały czas pamiętać). Wychodzą z niego cztery krawędzie które wyznaczają cztery wierzchołki. Mamy więc już narysowanych pięć wierzchołków. W grafie są jeszcze dwa więc je rysuje gdzieś obok. Teraz zaczyna się kombinowanie. Przyjmuje sobie np. że jeden z wierzchołków połączonych z wierzchołkiem stopnia cztery jest stopnia jeden i piszę sobie przy nim jedynkę. Teraz przypuśćmy że jeden z wierzchołków połączonych z wierzchołkiem st. 4 ma np. stopień dwa. No i próbuje coś tam rysować i sprawdzać czy mi wyjdzie. Jak nie wychodzi no to trzeba wziąć jakiś wierzchołek nie połączony z wierzchołkiem stopnia 4 i nadać mu stopień dwa. No grafy ogólnie polegają na takim kombinowaniu. Nie ma tu chyba jakiejś głębszej metody. Trzeba kombinować :)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ilość parowań wierzchołków grafu
Ile jest różnych doskonałych parowań grafu (drabiny; tak jak na rysunku poniżej) o 2n wierzchołkach (czyli n wierzchołków na dole i n na górze)? Rozpatrzeć przypad...
 forever17  2
 Algorytm Dijkstry - odtworzenie grafu
Witam. Mam problem z następującym zadaniem. Będę wdzięczny za pomoc. Po zastosowaniu dla pewnego grafu algorytmu Dijkstry poszukujące-go najkrótszych ścieżek z wierzchołka v_{2} otrzymano na końcu następujące wektory ety...
 PoisonPrince  0
 Skojarzenie doskonałe grafu dwudzielnego
Zadanie: Wykaż, że graf dwudzielny regularny posiada skojarzenie doskonałe. Wszelkie pomysły mile widziane. Z góry dzięki....
 Szemek  6
 Eulerowkość grafu
Dla jakich n graf pełny Kn jest eulerowski, semi-eulerowski....
 zielony789  0
 Kolorowanie grafu - artykuł
Bo ja wiem, co bym napisał? Ale od razu na myśl przychodzi mi tu twierdzenie Ramseya. Jest opisane w książce Lipskiego i Marka "Analiza kombinatoryczna". Orzeka ono m. in. że jeśli mamy graf pełny K_6 (tzn. każd...
 wiedzmac  4
 Średnica grafu samodopełniającego
Witam. Mam problem z zadaniem: Dowieść, że dla grafu samodopełniającego G i ma co najmniej 2 wierzchołki, to zachodzi nierówność: diam(G) \le 3. Z góry dzięki za pomoc ...
 kubek1  0
 Liczba sposobów pokolorowania grafu
Ale w ten sposób każde kolorowanie liczysz trzykrotnie. Kolorowań trzema kolorami jest równa \frac{n(n-1)(n-2)}3. Trochę nie rozumiem dlaczego tak, ale...
 MathNoob  18
 Kolorowanie grafu - zadanie 2
Witam, Mam problem z poniższym zadaniem: Punkty K, L, M, N są odpowiednio środkami boków AB, BC, CD, DA kwadratu ABCD. Każdy punkt A, B, C, D, K, ...
 bartm  2
 Liczba chromatyczna grafu
Cześć, Mam problem z zadaniem: Uzasadnić że dla grafu o m krawędziach prawdziwa jest nierówność \chi(G) < 0,5 + \sqrt{0,25 + 2|E|} Nie wiem od czego zacząć. Myślałem, żeby zad...
 poczatkujacy_ja  0
 Dwuspójność grafu krytycznego
Jak wyżej. Mam zadanie "Pokazać, że każdy graf krytyczny jest dwuspójny". Niestety, pomimo prób, nie mogę tego rozwiązać, ani znaleść rozwiązania tego problemu na necie. Ktoś umie to rozwiązać i objaśnić?...
 duga3  0
 Wielomian chromatyczny grafu K_3,3
Chcę znaleźć wielomian chromatyczny grafu K_{3,3}. Na wikipedii napisali, że za różne uznajemy takie kolorowania, która różnią się nawet tylko permutacją kolorów. Wydaje mi się, że będzie tak: P_{K_{3,3}}&#...
 Heniek1991  5
 Ilość podgrafów grafu K10 izomorficznych z W6 (gwazda 6)
Tak jak w tytule, polecenie brzmi, znajdz ilość podgrafów pełnego grafu K10 izomorficznych z W6 (gwiazdą 6). Mój sposób rozumowania: Wariacje bez powtórzeń 5 z 10 * kombinacje 1 z 5 / 2 = 10!/5! * 1/2 * 5 = 75600 Wybieram wariacje bez powtór...
 chmielusek  2
 Liczb chromatyczna grafu, a zbiór niezależny
Witam, potrzebuję pomocy z udowodnieniem tezy: \alpha (G) \ge \frac{n}{ \beta (G)} gdzie: \alpha (G) - liczba wierzchołków największego zbioru niezależnego w grafie ...
 mqtqbenc  1
 Udowodnij, że krawędzie dowolnego grafu nieskierowanego
Witam, Udowodnij, że krawędzie dowolnego grafu nieskierowanego można skierować w taki sposób, że dla każdego wierzchołka v spełniony będzie warunek: |\deg_{in}(v) -\deg_{out}(v)}|\le 1[/tex:...
 matinf  1
 Nierówność między średnicą a promieniem grafu prostego
Udowodnić, że diam(G) \le 2rad(G), gdzie diam(G)=max\{dist(x,y)\} - średnica grafu, a rad(G)=min_{x}max_y\{dist(x,y)\}[/tex:owxg15...
 klaudiak  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com