Μητροειδή και Εφαρμογές Αυτών

Abstract

The concept of Matroid was first defined by Whitney in 1935 as an abstract generalization of graphs and tables. The term refers to the mathematical term matrix (ie matrix). Both in Graph Theory, elements of which were presented in chapter 6, and in linear algebra, where the matrices and their properties are presented, dependency relations between graphs or in vector matrices. Whitney succeeded with this structure on the one hand in connecting special categories graphs with tables, on the one hand to capture the essence of the abstract concept of dependence. In two decades that followed the introduction of the matriline concept, comparatively few results were published. Only since the mid-1950s has progress been made, and at an ever-increasing rate. Since when this chapter was written, there was an extensive work published with many important ones theorems, only a small part of them was selected. The results to be presented are used to solve difficult problems in various fields such as politics, energy, mechanical engineering, computer science and mathematics. Matroids can be viewed as generalized geometries, and are therefore included also in Combination. For Combinatorialism, a matroid is nothing but a structure which encapsulates but also generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid. The most widespread is the one that expresses the matroid, in terms of independent sets, bases, circuits, closed sets, inclusion operators and arrangement. Let it be noted that graphs are forms, like those which concern geometries, but as and those dealt with by Syndyastica. As regards the relation of matroids to graphs, in this theory only special classes of graphs are included, such as complete, Kuratowski graphs etc. Matroids describe these forms, but they also describe a surprising variety clusters. A classic example of the relationship that combinatorics has with graph theory is the elationship of arrangements with trees (a-circle graphs). In addition, matroids allow the development of methods optimizations in combinatorial analysis, since they are precisely the structures for which the greedy algorithm works. With the term "Combination Optimization" in the Theoretical Science of By computers we understand the set of propositions which allow the development of algorithms for selecting an optimal object from a finite set of objects. From what the author knows, the evolution of the theory of matroids to date deals with problems for which the set of possible solutions is distinct or can be represented by distinct sets of solutions. Target is to identify the best solution. From what was developed in the chapter on the Scriptures, we mention as a Combinatorial Optimization problem the traveling salesman problem and the problem minimum weight spanning tree detection. In this chapter the theory of matroids is introduced, some of the basic theorems are presented and some of the most important problems that retain a strong interest in the are identified their applications. Despite the fact of the exceptional bibliographic breadth, in this electronic book elements of the theory concerning: the Basic Definitions and Important have been selected for presentation Theorems, Matroids and Graphs and finally Greedy Algorithms and Matroids.

Η θεωρία Μητροειδών συνδέει και γενικεύει πολλά στοιχεία της Γραμμική Άλγεβρας , της Συνδυαστικής και της Θεωρίας Γραφημάτων. Μπορούμε να την θεωρήσουμε ως μια αφαίρεση των διαφόρων εννοιών πρωτεύουσας σημασίας σε αυτούς τους τομείς. Μητροειδή έχουν βρει εφαρμογές στη Γεωμετρία, Τοπολογία, Συνδυαστική Βελτιστοποίηση, στη θεωρία του Δικτύου και τη Θεωρία Κωδικοποίησης. Σε αυτήν την ενότητα σκοπεύουμε να παρουσιάσουμε τις βασικές ιδέες και θεωρήματα που διαμορφώνουν την θεωρία Μητροειδών.