Pengguna:Chinamoonroll/bak pasir

Darajat Geothermal Power Plant

Darajat Power Plant Complex
Negara	Indonesia
Koordinat	07°21′05″S 107°13′37″E
Status	Operasional
Biaya pembangunan	>US$200 million
Operator	Indonesian Electricity Company (Unit I) PT Chevron Geothermal Indonesia & Pertamina (Unit II & III)

Darajat Georhermal Power Plant Complex which is situated in District Pasirwangi, Garut, West Java, is on the flanks of Mt Kendang, roughly 150 km south-east of Jakarta. The asset is inside a volcanic range containing focuses of generally ongoing action. The asset is situated in steep and tough landscape, somewhere in the range of 2000 meters above ocean level. The Darajat geothermal field is a generous excellent asset delivering dry steam at the wellhead; and incorporates some enormous wells (40 MW limit from one well - the overall normal is 5-10 MW/well). The asset is one of just a couple of dry steam fields on the planet.

Pohon rentangan minimum

Minimum spanning tree

Sebuah graf planar dan pohon rentangan minimumnya. Setiap tepi diberi label dengan bobot, yang kira - kira sebanding dengan panjangnya.

Pohon rentangan minimum atau pohon retangan bobot minimum atau Inggris: minimum spanning tree (MST) adalah subset dari tepi terhubung, graf tidak berarah tepi-berbobot yang menghubungkan semua simpul bersamaan, tepi-berbobot pada graf tidak berarah menghubungkan simpul bersama, tanpa siklus dan dengan total bobot tepi minimum yang dimungkinkan. Artinya, pohon rentangan yang jumlah bobot tepi sekecil mungkin. Secara lebih umum, setiap graf tidak berarah berbobot tepi (tidak harus terhubung) memiliki hutan rentangan minimum, yang merupakan gabungan dari MST untuk komponen terhubung.

Ada beberapa kasus penggunaan MST, Salah satu contohnya adalah perusahaan telekomunikasi yang mencoba memasang kabel di lingkungan baru. Jika dibatasi untuk memasang kabel hanya di sepanjang jalur tertentu (mis. Jalan), maka akan ada grafik yang berisi titik (mis. Rumah) yang terhubung oleh jalur tersebut. Beberapa jalur mungkin lebih mahal, karena lebih panjang, atau membutuhkan kabel untuk ditanam lebih dalam;jalur ini akan diwakili oleh tepi dengan bobot lebih besar. Mata uang adalah unit yang dapat diterima untuk berat tepi, tidak ada persyaratan panjang tepi untuk mematuhi aturan geometri normal seperti ketidaksamaan segitiga. Pohon rentangan untuk graf tersebut akan menjadi bagian dari jalur yang tidak memiliki siklus tetapi masih menghubungkan setiap simpul; mungkin ada beberapa pohon merentang lainya. MST akan menjadi pohon dengan biaya total terendah, mewakili jalur paling murah untuk memasang kabel.

Properti

Possible multiplicity

If there are n vertices in the graph, then each spanning tree has n − 1 edges.

This figure shows there may be more than one minimum spanning tree in a graph. In the figure, the two trees below the graph are two possibilities of minimum spanning tree of the given graph.

There may be several minimum spanning trees of the same weight; in particular, if all the edge weights of a given graph are the same, then every spanning tree of that graph is minimum.

Uniqueness

If each edge has a distinct weight then there will be only one, unique minimum spanning tree. This is true in many realistic situations, such as the telecommunications company example above, where it's unlikely any two paths have exactly the same cost. This generalizes to spanning forests as well.

Proof:

1. Assume the contrary, that there are two different MSTs A and B.
2. Since A and B differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let e₁ be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume e₁ is in A.
3. As B is an MST, {e₁} $\cup$ B must contain a cycle C with e₁.
4. As a tree, A contains no cycles, therefore C must have an edge e₂ that is not in A.
5. Since e₁ was chosen as the unique lowest-weight edge among those belonging to exactly one of A and B, the weight of e₂ must be greater than the weight of e₁.
6. As e₁ and e₂ are part of the cycle C, replacing e₂ with e₁ in B therefore yields a spanning tree with a smaller weight.
7. This contradicts the assumption that B is a MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.

Minimum-cost subgraph

If the weights are positive, then a minimum spanning tree is in fact a minimum-cost subgraph connecting all vertices, since subgraphs containing cycles necessarily have more total weight.

Cycle property

For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to an MST.

Proof: Assume the contrary, i.e. that e belongs to an MST T₁. Then deleting e will break T₁ into two subtrees with the two ends of e in different subtrees. The remainder of C reconnects the subtrees, hence there is an edge f of C with ends in different subtrees, i.e., it reconnects the subtrees into a tree T₂ with weight less than that of T₁, because the weight of f is less than the weight of e.

Cut property

This figure shows the cut property of MSTs. T is the only MST of the given graph. If S = {A,B,D,E}, thus V-S = {C,F}, then there are 3 possibilities of the edge across the cut(S,V-S), they are edges BC, EC, EF of the original graph. Then, e is one of the minimum-weight-edge for the cut, therefore S ∪ {e} is part of the MST T.

For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

Proof: Assume that there is an MST T that does not contain e. Adding e to T will produce a cycle, that crosses the cut once at e and crosses back at another edge e' . Deleting e' we get a spanning tree T∖{e'}∪{e} of strictly smaller weight than T. This contradicts the assumption that T was a MST.

By a similar argument, if more than one edge is of minimum weight across a cut, then each such edge is contained in some minimum spanning tree.

Minimum-cost edge

If the minimum cost edge e of a graph is unique, then this edge is included in any MST.

Proof: if e was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight.

Contraction

If T is a tree of MST edges, then we can contract T into a single vertex while maintaining the invariant that the MST of the contracted graph plus T gives the MST for the graph before contraction.

Algorithms

In all of the algorithms below, m is the number of edges in the graph and n is the number of vertices.

Classic algorithms

The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926 (see Borůvka's algorithm). Its purpose was an efficient electrical coverage of Moravia. The algorithm proceeds in a sequence of stages. In each stage, called Boruvka step, it identifies a forest F consisting of the minimum-weight edge incident to each vertex in the graph G, then forms the graph $G_{1}=G\setminus F$ as the input to the next step. Here $G\setminus F$ denotes the graph derived from G by contracting edges in F (by the Cut property, these edges belong to the MST). Each Boruvka step takes linear time. Since the number of vertices is reduced by at least half in each step, Boruvka's algorithm takes O(m log n) time.

A second algorithm is Prim's algorithm, which was invented by Vojtěch Jarník in 1930 and rediscovered by Prim in 1957 and Dijkstra in 1959. Basically, it grows the MST (T) one edge at a time. Initially, T contains an arbitrary vertex. In each step, T is augmented with a least-weight edge (x,y) such that x is in T and y is not yet in T. By the Cut property, all edges added to T are in the MST. Its run-time is either O(m log n) or O(m + n log n), depending on the data-structures used.

A third algorithm commonly in use is Kruskal's algorithm, which also takes O(m log n) time.

A fourth algorithm, not as commonly used, is the reverse-delete algorithm, which is the reverse of Kruskal's algorithm. Its runtime is O(m log n (log log n)³).

All these four are greedy algorithms. Since they run in polynomial time, the problem of finding such trees is in FP, and related decision problems such as determining whether a particular edge is in the MST or determining if the minimum total weight exceeds a certain value are in P.

Faster algorithms

Several researchers have tried to find more computationally-efficient algorithms.

In a comparison model, in which the only allowed operations on edge weights are pairwise comparisons, (Karger, Klein & Tarjan 1995) found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm.

The fastest non-randomized comparison-based algorithm with known complexity, by Bernard Chazelle, is based on the soft heap, an approximate priority queue. Its running time is O(m α(m,n)), where α is the classical functional inverse of the Ackermann function. The function α grows extremely slowly, so that for all practical purposes it may be considered a constant no greater than 4; thus Chazelle's algorithm takes very close to linear time.

Linear-time algorithms in special cases

Dense graphs

If the graph is dense (i.e. m/n ≥ log log log n), then a deterministic algorithm by Fredman and Tarjan finds the MST in time O(m). The algorithm executes a number of phases. Each phase executes Prim's algorithm many times, each for a limited number of steps. The run-time of each phase is O(m+n). If the number of vertices before a phase is $n'$, the number of vertices remaining after a phase is at most $n'/2^{m/n'}$. Hence, at most $\log ^{*}{n}$ phases are needed, which gives a linear run-time for dense graphs.

There are other algorithms that work in linear time on dense graphs.

Integer weights

If the edge weights are integers represented in binary, then deterministic algorithms are known that solve the problem in O(m + n) integer operations. Whether the problem can be solved deterministically for a general graph in linear time by a comparison-based algorithm remains an open question.

Decision trees

Given graph G where the nodes and edges are fixed but the weights are unknown, it is possible to construct a binary decision tree (DT) for calculating the MST for any permutation of weights. Each internal node of the DT contains a comparison between two edges, e.g. "Is the weight of the edge between x and y larger than the weight of the edge between w and z?". The two children of the node correspond to the two possible answers "yes" or "no". In each leaf of the DT, there is a list of edges from G that correspond to an MST. The runtime complexity of a DT is the largest number of queries required to find the MST, which is just the depth of the DT. A DT for a graph G is called optimal if it has the smallest depth of all correct DTs for G.

For every integer r, it is possible to find optimal decision trees for all graphs on r vertices by brute-force search. This search proceeds in two steps.

A. Generating all potential DTs

• There are $2^{r \choose 2}$ different graphs on r vertices.
• For each graph, an MST can always be found using r(r-1) comparisons, e.g. by Prim's algorithm.
• Hence, the depth of an optimal DT is less than $r^{2}$.
• Hence, the number of internal nodes in an optimal DT is less than $2^{r^{2}}$.
• Every internal node compares two edges. The number of edges is at most $r^{2}$ so the different number of comparisons is at most $r^{4}$.
• Hence, the number of potential DTs is less than: ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$.

B. Identifying the correct DTs To check if a DT is correct, it should be checked on all possible permutations of the edge weights.

• The number of such permutations is at most $(r^{2})!$.
• For each permutation, solve the MST problem on the given graph using any existing algorithm, and compare the result to the answer given by the DT.
• The running time of any MST algorithm is at most $(r^{2})$, so the total time required to check all permutations is at most $(r^{2}+1)!$.

Hence, the total time required for finding an optimal DT for all graphs with r vertices is: $2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!$, which is less than: $2^{2^{r^{2}+o(r)}}$.

Lihat pula: Decision tree model

Optimal algorithm

Seth Pettie and Vijaya Ramachandran have found a provably optimal deterministic comparison-based minimum spanning tree algorithm. The following is a simplified description of the algorithm.

1. Let $r=\log \log \log n$, where n is the number of vertices. Find all optimal decision trees on r vertices. This can be done in time O(n) (see Decision trees above).
2. Partition the graph to components with at most r vertices in each component. This partition uses a soft heap, which "corrupts" a small number of the edges of the graph.
3. Use the optimal decision trees to find an MST for the uncorrupted subgraph within each component.
4. Contract each connected component spanned by the MSTs to a single vertex, and apply any algorithm which works on dense graphs in time O(m) to the contraction of the uncorrupted subgraph
5. Add back the corrupted edges to the resulting forest to form a subgraph guaranteed to contain the minimum spanning tree, and smaller by a constant factor than the starting graph. Apply the optimal algorithm recursively to this graph.

The runtime of all steps in the algorithm is O(m), except for the step of using the decision trees. We don't know the runtime of this step, but we know that it is optimal - no algorithm can do better than the optimal decision tree.

Thus, this algorithm has the peculiar property that it is provably optimal although its runtime complexity is unknown.

Parallel and distributed algorithms

Informasi lebih lanjut: Parallel algorithms for minimum spanning trees

Research has also considered parallel algorithms for the minimum spanning tree problem. With a linear number of processors it is possible to solve the problem in $O(\log n)$ time. (Bader & Cong 2006) demonstrate an algorithm that can compute MSTs 5 times faster on 8 processors than an optimized sequential algorithm.

Other specialized algorithms have been designed for computing minimum spanning trees of a graph so large that most of it must be stored on disk at all times. These external storage algorithms, for example as described in "Engineering an External Memory Minimum Spanning Tree Algorithm" by Roman, Dementiev et al., can operate, by authors' claims, as little as 2 to 5 times slower than a traditional in-memory algorithm. They rely on efficient external storage sorting algorithms and on graph contraction techniques for reducing the graph's size efficiently.

The problem can also be approached in a distributed manner. If each node is considered a computer and no node knows anything except its own connected links, one can still calculate the distributed minimum spanning tree.

MST on complete graphs

Alan M. Frieze showed that given a complete graph on n vertices, with edge weights that are independent identically distributed random variables with distribution function $F$ satisfying $F'(0)>0$, then as n approaches +∞ the expected weight of the MST approaches $\zeta (3)/F'(0)$, where $\zeta$ is the Riemann zeta function (more specifically is $\zeta (3)$ Apéry's constant). Frieze and Steele also proved convergence in probability. Svante Janson proved a central limit theorem for weight of the MST.

For uniform random weights in $[0,1]$, the exact expected size of the minimum spanning tree has been computed for small complete graphs.

Vertices	Expected size	Approximate expected size
2	1 / 2	0.5
3	3 / 4	0.75
4	31 / 35	0.8857143
5	893 / 924	0.9664502
6	278 / 273	1.0183151
7	30739 / 29172	1.053716
8	199462271 / 184848378	1.0790588
9	126510063932 / 115228853025	1.0979027

Penerapan

Pohon rentangan minimum memiliki penerapan langsung dalam desain jaringan, termasuk jaringan komputer, jaringan telekomunikasi, jaringan transportasi, jaringan pasokan air, dan jaringan listrik (yang pertama kali mereka temukan, seperti yang disebutkan di atas). Mereka digunakan sebagai subrutin dalam algoritma untuk masalah lain, termasuk algoritma Christofides untuk pendekatan masalah penjual keliling, pendekatan masalah pemotongan minimum multi-terminal (yang setara dalam kasus terminal tunggal dengan masalah aliran maksimum), dan pendekatan sempurna pencocokan berbobot berbiaya minimum.

Penerapan lainnya berdasarkan pohon rentangan minimum meliputi:

• Taksonomi.
• Analisis Klaster: titil klaster pada pesawat, pengelompokan hubungan tunggal (metode pengelompokan hierarki), graph-theoretic clustering, and clustering gene expression data.
• Membangun pohon untuk penyiaran pada jaringan komputer.
• Pendaftaran citra dan segmantasi – lihat segmentasi berbasis pohon rentang minimum.
• Curvilinear ekstraksi fitur di pencitraan komputer.
• Handwriting recognition of mathematical expressions.
• Circuit design: implementing efficient multiple constant multiplications, as used in finite impulse response filters.
• Regionalisation of socio-geographic areas, the grouping of areas into homogeneous, contiguous regions.
• Comparing ecotoxicology data.
• Topological observability in power systems.
• Measuring homogeneity of two-dimensional materials.
• Minimax process control.
• Minimum spanning trees can also be used to describe financial markets. A correlation matrix can be created by calculating a coefficient of correlation between any two stocks. This matrix can be represented topologically as a complex network and a minimum spanning tree can be constructed to visualize relationships.

Masalah terkait

Pohon Steiner miminum dengan simpul poligon reguler N = 3 hingga 8 sisi. Panjang jaringan terendah L untuk N > 5 adalah keliling kurang satu sisi. Kotak mewakili poin Steiner.

Masalah menemukan pohon Steiner dari himpunan bagian dari simpul, yaitu, pohon minimum yang merentang bagian yang diberikan, dikenal sebagai NP-Lengkap.

Masalah terkait adalah pohon rentang k-minimum (k-MST), yang merupakan pohon yang merentang beberapa bagian dari simpul k pada graf dengan berat minimum.

Seperangkat pohon spanning k-terkecil adalah subset dari pohon rentang (dari semua pohon rentang yang memungkinkan) sehingga tidak ada pohon rentang di luar subset yang memiliki bobot lebih kecil. (Perhatikan bahwa masalah ini tidak terkait dengan pohon rentang k-minimum.)

Pohon rentangan minimun Euclidean adalah pohon rentang dari graf dengan bobot tepi yang sesuai dengan jarak Euclidean antara simpul yang merupakan titik pada bidang (atau ruang).

pohon rentangan minimum rectilinear adalah pohon rentang dari grafik dengan bobot tepi yang sesuai dengan jarak rectilinear antara simpul yang merupakan titik dalam bidang (atau ruang).

Dalam model terdistribusi, di mana setiap node dianggap sebagai komputer dan tidak ada node yang tahu apa pun kecuali tautan yang terhubung sendiri, seseorang dapat mempertimbangkan pohon rentang minimum terdistribusi. Definisi matematis dari masalahnya adalah sama tetapi ada pendekatan yang berbeda untuk suatu solusi.

Pohon rentangan minimum berkapasitas adalah pohon yang memiliki simpul yang ditandai (asal, atau root) dan masing-masing subtree yang melekat pada node tidak lebih dari node c. c disebut kapasitas pohon. Memecahkan CMST secara optimal adalah NP-hard,

Pohon yang dibatasi derajat minimum adalah pohon rentangan minimum di mana setiap titik terhubung ke tidak lebih dari d simpul lainnya, untuk beberapa angka tertentu d. Kasus d = 2 adalah kasus khusus dari masalah penjual keliling, jadi tingkat batasan pohon rentang minimum adalah NP-hard secara umum.

Untuk graf berarah, masalah spanning tree minimum disebut masalah Arborescence dan dapat diselesaikan dalam waktu kuadratik menggunakan algoritma Chu-Liu/Edmonds.

Pohon rentangan maksimum adalah pohon rentangan dengan bobot lebih besar atau sama dengan berat setiap pohon rentangan lainnya. Pohon seperti itu dapat ditemukan dengan algoritma seperti Prim atau Kruskal setelah mengalikan bobot tepi dengan -1 dan menyelesaikan masalah MST pada grafik baru. Jalur di pohon rentang maksimum adalah jalur terluas dalam grafik di antara dua titik akhir: di antara semua jalur yang mungkin, ia memaksimalkan bobot berat-minimum tepi. Pohon rentangan maksimum aplikasi pencarian dalam algoritma parsing untuk bahasa alami dan dalam algoritma pelatihan untuk bidang acak bersyarat.

Masalah MST dinamis berkaitan dengan pembaruan MST yang sebelumnya dihitung setelah perubahan bobot tepi pada graf asli atau penyisipan / penghapusan titik.

Masalah pohon rentangan minimum adalah menemukan pohon rentangan dengan jenis label paling sedikit jika setiap sisi dalam graf dikaitkan dengan label dari label hingga, bukan bobot.

Tepi bottleneck adalah tepi berbobot tertinggi di pohon rentangan. Pohon rentangan adalah 'pohon rentangan ''bottleneck'' minimum' (atau 'MBST' ) jika graf tidak mengandung pohon rentangan dengan bobot tepi bottleneck yang lebih kecil. MST harus merupakan MBST (dapat dibuktikan oleh properti potong)), tetapi MBST tidak harus berupa MST.

Bacaan lanjutan

• Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's.)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp. 561–579.
• Eisner, Jason (1997). State-of-the-art algorithms for minimum spanning trees: A tutorial discussion. Manuscript, University of Pennsylvania, April. 78 pp.
• Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Using minimum spanning tree as method of demographic analysis of ethnic diversity across the United States).

Pranala luar

• Implemented in BGL, the Boost Graph Library
• The Stony Brook Algorithm Repository - Minimum Spanning Tree codes
• Implemented in QuickGraph for .Net