Yeni Kayıt
Konudaki Resimler
|
|
_____________________________
|
Bildirim
Graflar
Sıcak Fırsatlarda Tıklananlar
Editörün Seçtiği Fırsatlar
Daha Fazla 
Bu Konudaki Kullanıcılar:
Daha Az 
2 Misafir - 2 Masaüstü
Giriş
Mesaj
-
-
Grafları polinomsal olarak çözmek? Grafın neyini çözeceksin biraz daha bahsetsen güzel olur. "Grafı çözmek" 'den anladığın ne? _____________________________ -
Oncelikle Polinom cozmek diye birsey nedir?
NP nin P yi kapsadigini biliyoruz ama NP P mi degil mi bilmiyoruz. Buna gore sorunun cozumu P ama NP degil olacak cozumler var, veya NP olup cozulcek sorular var.
Simdi NP olan atiyorum Travelling Salesman falan var bunu approximation ile P zamanda cozebiliyorsun.
Onun disinda direk algoritmalarin cogu zaten P atiyorum Floyd Warshall in Dinamik cozumu O(V^3) dur bu da dolayisiyla hem polinom hemde non polinomdur.
< Bu mesaj bu kişi tarafından değiştirildi ThisisaNightmare -- 5 Şubat 2014; 10:22:38 >_____________________________ -
Chromatic polinom olarakta geçer mesela graf renklendirmede kullanılacak en az renk sayısını bulma gibi _____________________________ -
quote:
Orijinalden alıntı: badboy39
Chromatic polinom olarakta geçer mesela graf renklendirmede kullanılacak en az renk sayısını bulma gibi
Bende Polinom(polynomial) zamanda cozulecek grafik algoritmalari anladim._____________________________ -
@badboy39Chromatic Polynomial için öncelikle belli başlı graph türlerinin polinomları var. İşte atıyorum complete graph için, cycle için vesaire. Normalde, graphı enterpole etmen lazım ama bu algoritma hiç sağlıklı değil ömür geçer. Bunun yerine Birkhoff-Lewis teoremini kullanabilirsin. Bu, belli şartları sağlayan iki vertex'i, tek bir vertex'e reduce etmek suretiyle graphı kromatik polinomlarını daha önceden bildiğimiz graphlara indirgemedir aslında. Bu indirgenmiş haldeki graphların kromatik polinomları ile asıl graphın kromatik polinomu arasındaki bağıntı ilk defa Lewis tarafından ortaya koyulmuştu. Zaten hemen arkasından sağolsun mühendisler bunu recursive olarak denediler. Gayet güzel sonuçlar aldılar. Ben Birkhoff'un makalesini kullanmıştım Ayrık Matematik dersinde açıkçası.
< Bu mesaj bu kişi tarafından değiştirildi spartico -- 9 Şubat 2014; 20:52:59 >_____________________________
Sayfa:
1
Ip işlemleri
Bu mesaj IP'si ile atılan mesajları ara Bu kullanıcının son IP'si ile atılan mesajları ara Bu mesaj IP'si ile kullanıcı ara Bu kullanıcının son IP'si ile kullanıcı ara
KAPAT X
Bu mesaj IP'si ile atılan mesajları ara Bu kullanıcının son IP'si ile atılan mesajları ara Bu mesaj IP'si ile kullanıcı ara Bu kullanıcının son IP'si ile kullanıcı ara
KAPAT X
