The integrity of a graph G=(V,E) is defined as I(G)=min{|S|+m(G-S):SÍV(G))}, where m(G-X) denotes the order
of the largest component in the graph G-X. This is a better parameter to measure
the stability of a network, as it takes into account both the amount of work
done to damage the network and how badly the network is damaged. Computationally
it belongs to the class of intractable problems known as NP-Complete. In this
paper we develop a heuristic algorithm to determine the integrity of a graph.
Extensive computational experience on 88 randomly generated graphs ranging from
20% to 90% densities and from 100 to 200 vertices has shown that the proposed
algorithm is very effective.
Generating r-combinations of the set N={1, 2, …, n} in
lexicographical order has been an interest for researchers in the field of
computer science and combinatorial optimization. This study provides three new
algorithms for generating these r-combinations
in lexicographical order for the given n
and r. The first two of these
algorithms generate all the combinations by using a backtracking process. The
third algorithm directly generates the k-th
sequence in the lexicographical order by using a hash function. All these
algorithms perform an efficient running time compared to the well-known methods
used in literature.
Matrices are commonly used data structures in computer science. There do not exist available structures in programming languages for the special type of matrices such as triangular matrix. If it is required to use a triangular matrix as a data structure, then softwares are coded with inefficient space and time complexity due to the lack of data structure of a programming language. In this paper, transformation and inverse transformation formulae to be used for representing the triangular matrices as a one dimensional array are gathered and an increase in the amount of efficiency of a program in terms of space and time complexity is objected.
Keywords: Domination; independent domination; strong weak domination, mathematical programming
Macar algoritması bilgisayar bilimleri literatüründe en çok bilinen yöntemlerden birisidir. Bu yöntem ile maliyet matrisi her adımda sistematik bir şekilde yeni bir indirgenmiş matrise dönüştürülerek atama problemine çözüm getirilmektedir. Algoritmanın alt yordamında matriste sıfır içeren tüm hücreler en az sayıda çizgi ile kapatılmakta ve çizgilerin durumuna göre matris üzerinde işlem yapılmaktadır. Bu makalede literatürdeki en az sayıda çizgi ile kapatma teknikleri incelenecek ve yeni bir yöntem önerisinde bulunularak hesaplama denemelerinin sonuçları tartışılacaktır.
Katılımcıların n adet sayı
arasından r tanesini
seçerek kupona işaretlediği ve çekilişe katıldığı oyunlar kombinasyon tipi
oyunlar sınıfına girer, bu oyunlarda topların çıkış sırasının önemi yoktur ve
çekiliş sonucunda sayılar küçükten büyüğe sıralı olarak ilan edilir. Teorik
olarak, olası tüm çekilişler yani ilgili oyuna ait tüm kombinasyonlar dikkate
alınırsa bazı sayıların belirli sıralarda diğerlerinden daha çok yer alması
gerektiği görülmektedir. Pratikte de ilgili oyuna ait çekiliş sayısı arttıkça
gözlenen değerlerin beklenen değerlere yaklaştığı görülmektedir. Bu çalışmada
Milli Piyango İdaresi tarafından oynatılan şans oyunlarının her biri için hangi
sayıların hangi sırada daha çok gözlenmesi gerektiği teorik olarak incelenecek
ve pratikte ki sonuçlar ile karşılaştırılacaktır.
Permütasyon,
n elemanlı bir kümenin r elemanlı alt kümelerinin elemanlar arasında sıra
gözetilmek suretiyle kaç farklı şekilde düzenlenebileceğini bulmak için
kullanılan matematiksel bir ifadedir. Düzenlemelerin sadece sayısı ile
ilgilenilmeyip aynı zamanda üretilmesi ve yazdırılması da gerekiyorsa özyineleme
ve geri yönde izleme tekniklerini kullanan algoritmalar ile bu amaca
ulaşılabilmektedir. Ayrıca istenirse n'in r'li permütasyonları algoritmaya kısıt
ilave edilmesiyle sözlüksel sırada da üretilebilir. Bu çalışmada n elemanlı bir
kümenin r elemanlı tüm permütasyonları göz önüne alındığında hepsini üretmeye
gerek kalmadan sözlüksel olarak k. sırada yer alan permütasyonu yazdırmak için özet
fonksiyon kullanan bir algoritma önerilmiştir. Önerilen algoritma kodlanarak
hesaplama denemeleri yapılmış ve verimliliğinin yüksek olduğu görülmüştür.
