翻訳と辞書 Words near each other ・ Hypergeometric distribution ・ Hypergeometric function ・ Hypergeometric function of a matrix argument ・ Hypergeometric identity ・ Hypergeusia ・ Hypergiant ・ Hyperglide ・ Hyperglycemia ・ Hyperglycerolemia ・ Hyperglycinemia ・ Hypergol Maintenance Facility ・ Hypergolic propellant ・ Hypergonadism ・ Hypergonadotropic hypogonadism ・ Hypergranulosis ・ Hypergraph ・ Hypergraphia ・ Hypergraphic ・ Hypergraphy ・ Hypergravity ・ Hypergrowth ・ Hypergymnasia ・ Hyperharmonic number ・ Hyperhead ・ Hyperhidrosis ・ Hyperhomocysteinemia ・ Hyperhomology ・ Hyperhydricity ・ Hyperia ・ Hyperia galba Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Hypergraph ： ウィキペディア英語版 Hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can connect any number of vertices. Formally, a hypergraph $H$ is a pair $H\; =\; (X,E)$ where $X$ is a set of elements called ''nodes'' or ''vertices'', and $E$ is a set of non-empty subsets of $X$ called hyperedges or edges. Therefore, $E$ is a subset of $\backslash mathcal(X)\; \backslash setminus\backslash$, where $\backslash mathcal(X)$ is the power set of $X$. While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same cardinality; a ''k''-uniform hypergraph is a hypergraph such that all its hyperedges have size ''k''. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting ''k'' nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. A hypergraph is also called a set system or a family of sets drawn from the universal set ''X''. The difference between a set system and a hypergraph is in the questions being asked. Hypergraph theory tends to concern questions similar to those of graph theory, such as connectivity and colorability, while the theory of set systems tends to ask non-graph-theoretical questions, such as those of Sperner theory. There are variant definitions; sometimes edges must not be empty, and sometimes multiple edges, with the same set of nodes, are allowed. Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs. Hypergraphs have many other names. In computational geometry, a hypergraph may sometimes be called a range space and then the hyperedges are called ''ranges''.〔.〕 In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory. In some literature edges are referred to as hyperlinks or connectors.〔Judea Pearl, in ''HEURISTICS Intelligent Search Strategies for Computer Problem Solving'', Addison Wesley (1984), p. 25.〕 Special kinds of hypergraphs include, besides ''k''-uniform ones, clutters, where no edge appears as a subset of another edge; and abstract simplicial complexes, which contain all subsets of every edge. The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms. ==Terminology== Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''. Let $H=(X,E)$ be the hypergraph consisting of vertices :$X\; =\; \backslash lbrace\; x\_i\; |\; i\; \backslash in\; I\_v\; \backslash rbrace,$ and having ''edge set'' :$E\; =\; \backslash lbrace\; e\_i\; |\; i\backslash in\; I\_e,\; e\_i\; \backslash subseteq\; X\; \backslash rbrace,$ where $I\_v$ and $I\_e$ are the index sets of the vertices and edges respectively. A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph $H\_A$ induced by a subset $A$ of $X$ is defined as :$H\_A=\backslash left(A,\; \backslash lbrace\; e\_i\; \backslash cap\; A\; |$ e_i \cap A \neq \varnothing \rbrace \right). The partial hypergraph is a hypergraph with some edges removed. Given a subset $J\; \backslash subset\; I\_e$ of the edge index set, the partial hypergraph generated by $J$ is the hypergraph :$\backslash left(X,\; \backslash lbrace\; e\_i\; |\; i\backslash in\; J\; \backslash rbrace\; \backslash right).$ Given a subset $A\backslash subseteq\; X$, the section hypergraph is the partial hypergraph :$H\; \backslash times\; A\; =\; \backslash left(A,\; \backslash lbrace\; e\_i\; |$ i\in I_e, e_i \subseteq A \rbrace \right). The dual $H^$ * of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\backslash lbrace\; e\_i\; \backslash rbrace$ and whose edges are given by $\backslash lbrace\; X\_m\; \backslash rbrace$ where :$X\_m\; =\; \backslash lbrace\; e\_i\; |\; x\_m\; \backslash in\; e\_i\; \backslash rbrace.$ When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, i.e., :$\backslash left(H^$ *\right)^ * = H. A connected graph ''G'' with the same vertex set as a connected hypergraph ''H'' is a host graph for ''H'' if every hyperedge of ''H'' induces a connected subgraph in ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the connected components of ''G'' and of ''H'', such that each connected component ''G''' of ''G'' is a host of the corresponding ''H'''. A hypergraph is bipartite if and only if its vertices can be partitioned into two classes ''U'' and ''V'' in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. The 2-section (or clique graph, representing graph, primal graph, Gaifman graph) of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hypergraph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.