algorytm.org

Ciąg graficzny(2)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Ciąg graficzny(2)
Ocena użytkowników:***** / 21
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 09 sierpnia 2005 19:42

Jeżeli należy wygenrować graf o zadanym ciągu stopni wierzchołków najpierw należy sprawdzić czy taki graf istnieje, czyli czy ciąg stopni jest graficzny. Można więc powiedzieć, ze dany ciąg liczb c=c1, c2, ..., cn jest graficzny jezeli istnieje graf o n wierzchołkach, dla którego c jest ciągiem stopni wierzchołków. Na przykład nie da się wygenerować grafu o 4 wierzchołkach i ciągu stopni 2,2,2,1.

Algorytm testowania czy ciąg jest graficzny przebiega następująco:
  • Posortuj ciąg c nierosnąco
  • Jeżeli wszystkie wyrazy ciagu są równe zeru to ciąg jest graficzny (czyli po posortowaniu c1 jest równe 0)
  • Jeżeli w ciągu c począwszy od drugiego elementu jest co najmniej c1 elementów o wartościach dodatnich, to odejmij 1 od c1 elementów ciągu począwszy od c2, podstaw 0 do c1 i wróc do kroku 1. Jeżeli w ciągu nie ma wystarczającej liczby elementów dodatnich to znaczy, że ciąg c nie jest graficzny
Przykład 1
n=5, c=2,3,2,3,2
posorutj ciąg: c=3,3,2,2,2
odejmij 1 od od c1 elementów ciągu począwszy od c2 podstaw 0 do c1 c=0,2,1,1,2
posorutj ciąg: c=2,2,1,1,0
odejmij 1 od od c1 elementów ciągu począwszy od c2 podstaw 0 do c1 c=0,1,0,1,0
posorutj ciąg: c=1,1,0,0,0
odejmij 1 od od c1 elementów ciągu począwszy od c2 podstaw 0 do c1 c=0,0,0,0,0
w ciągu zostały same zera a więc ciąg c=2,3,2,3,2
jest graficzny.

Przykład 2
n=5, c=1,4,2,3,1
posorutj ciąg: c=4,3,2,1,1
odejmij 1 od od c1 elementów ciągu począwszy od c2 podstaw 0 do c1 c=0,2,1,0,0
posorutj ciąg: c=2,1,0,0,0
w ciągu c począwszy od drugiego elementu nie ma c1 elementów o wartościach dodatnich a więc ciąg ten nie jest graficzny

Algorytm ten po pewnych modyfikacjach można wykorzystać do zdbudowania grafu o zadanym ciągu wierzchołków. Należy wierzchołek o maksymalnym stopniu w danej iteracji łączyć z wierzchołkami, w których zmniejszamy stopień o jeden. Ciag c musi w tym wypadku być ciągiem rekordów wartości i numeru wierzchołka, bo podczas losowania zmienia się kolejność ustawienia wierzchołków.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/Pascal
.pas
.pas
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2010 18:52
Komentarze
photo
+6 # JanJAn 2013-01-15 21:39
Prolog:


bubble_sort(Lis t,Sorted):-b_sort(List,[], Sorted).
b_sort([],Acc,A cc).
b_sort([H|T],Ac c,Sorted):-bubble(H,T,NT,M in),b_sort(NT,[ Min|Acc],Sorted ).
bubble(X,[],[], X).
bubble(X,[Y|T], [Y|NT],Min):-X=Y,bubble(Y,T,NT ,Min).

zmiejsz(H, 0, H).
zmiejsz([Hs|Ts] , Ile, [Hd|Td]) :- Ile > 0, Hd is Hs-1, Ile2 is Ile-1, zmiejsz(Ts, Ile2, Td).

czy_zerowe([0]) .
czy_zerowe([H|T ]) :- H = 0, czy_zerowe(T).

czy_ujemne([H|T ]) :- H < 0 ; czy_ujemne(T).
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz