Cette thèse s'inscrit dans le domaine de la théorie des hypergraphes et s'intéresse aux traverses minimales des hypergraphes. L'intérêt pour l'extraction des traverses minimales est en nette croissance, depuis plusieurs années, et ceci est principalement dû aux solutions qu'offrent les traverses minimales dans divers domaines d'application comme les bases de données, l'intelligence artificielle, l'e-commerce, le web sémantique, etc. Compte tenu donc du large éventail des domaines d'application des traverses minimales et de l'intérêt qu'elles suscitent, l'objectif de cette thèse est donc d'explorer de nouvelles pistes d'application des traverses minimales tout en proposant des méthodes pour optimiser leur extraction. Ceci a donné lieu à trois contributions proposées dans cette thèse. La première approche tend à tirer profit de l'émergence du Web 2.0 et, par conséquent, des réseaux sociaux en utilisant les traverses minimales pour la détection des acteurs importants au sein de ces réseaux. La deuxième partie de recherche au cours de cette thèse s'est intéressé à la réduction du nombre de traverses minimales d'un hypergraphe. Ce nombre étant très élevé, une représentation concise et exacte des traverses minimales a été proposée et est basée sur la construction d'un hypergraphe irrédondant, d'où sont calculées les traverses minimales irrédondantes de l'hypergraphe initial. Une application de cette représentation au problème de l'inférence des dépendances fonctionnelles a été présentée pour illustrer l’intérêt de cette approche. La dernière approche s'est intéressée à la décomposition des hypergraphes en des hypergraphes partiels. Les traverses minimales de ces derniers sont calculées et leur produit cartésien permet de générer l'ensemble des traverses de l'hypergraphe. Les différentes études expérimentales menées ont montré l’intérêt de ces approches proposées / This work is part of the field of the hypergraph theory and focuses on hypergraph minimal transversal. The problem of extracting the minimal transversals from a hypergraph received the interest of many researchers as shown the number of algorithms proposed in the literature, and this is mainly due to the solutions offered by the minimal transversal in various application areas such as databases, artificial intelligence, e-commerce, semantic web, etc. In view of the wide range of fields of minimal transversal application and the interest they generate, the objective of this thesis is to explore new application paths of minimal transversal by proposing methods to optimize the extraction. This has led to three proposed contributions in this thesis. The first approach takes advantage of the emergence of Web 2.0 and, therefore, social networks using minimal transversal for the detection of important actors within these networks. The second part of research in this thesis has focused on reducing the number of hypergraph minimal transversal. A concise and accurate representation of minimal transversal was proposed and is based on the construction of an irredundant hypergraph, hence are calculated the irredundant minimal transversal of the initial hypergraph. An application of this representation to the dependency inference problem is presented to illustrate the usefulness of this approach. The last approach includes the hypergraph decomposition into partial hypergraph the “local” minimal transversal are calculated and their Cartesian product can generate all the hypergraph transversal sets. Different experimental studies have shown the value of these proposed approaches

民主國家中選舉是獲得政治職位、聲望或權力的主要途徑之一，有許多因素會影響選舉結果，其中選舉制度是決定在位者與挑戰者去留的關鍵，決定如產生當選者，選舉制度往往會影響候選人的參選動機、競選方式、選民的投票行為，甚至會造成不同類型的政黨政治。本研究主要探究立委選舉從第七屆開始實行單一選區兩票制後，區域立委候選人的政治立場相較於過去在複數選區單記不可讓渡投票制下，是否有所不同或發生改變。本研究以兩岸議題為例，以第五屆及第七屆區域立法委員候選人為分析單位，並依其選舉公報採內容分析法為研究焦點。本研究有幾個研究發現：首先、選制改革有相當程度反映在屆別的差異上，對立委候選人兩岸立場造成影響；其次、雖然新選制下立委候選人提出更多的兩岸政見，但所提出的兩岸政見，新選制相較於舊選制，不但統獨立場趨中，且論述語氣略微和緩，此一發現支持中位選民定理，也就是說，在單一選區相對多數決制之下，立委候選人的兩岸議題不管在方向或是程度上，相較SNTV制度均有往中間靠攏的趨勢，意即新選制下的立委候選人在政見立場方向，是符合理論預期往意識形態光譜中間移動，傾向提出方向趨中且統獨維持現狀或中立的兩岸政見。 / In democratic country, election is the main approach for the politicians to receive position, reputation, and power. Many factors affect the result. Electoral system is one of the key causes to determine who-incumbent and challenger- will win the election. In addition, electoral systems also affect the process of producing winner, the candidates’ motive and campaign, the electorate’s voting behaviors. and even different types of party politics. This paper targets on the district legislators’ behaviors. Do their behaviors change after the electoral reform transiting from SNTV to Single-District Two-Votes System? To be more specific, I focus on the fifth and seventh terms of legislators as the analysis unit, and explore their attitudes or campaign platform on Cross-Strait issue, which are published on the campaign communique. I used the content analysis to analyze the campaign communique. There are several findings implied from this research. First, electoral system indeed affects legislators’ positions on Cross-Strait issues. There is significant difference between the fifth and seventh terms of legislators. Second, comparing with the fifth term, although the seventh term of legislators propose more Cross-Strait-related campaign platform, their attitudes are more moderate. This finding supports the median voter theorem. Under the Single-District System, comparing with SNTV, legislators will stand on moderate position on Cross-Strait issue, no matter on direction or intensity. In conclusion, the findings fit to my expectation that the seventh term of legislators stand on moderate position on the political spectrum. They are incline to propose more neutral campaign platform. They prefer maintaining the status quo to unification or independence.