|
Width Of A Hypergraph
In graph theory, there are two related properties of a hypergraph that are called its "width". Given a hypergraph ''H'' = (''V'', ''E''), we say that a set ''K'' of edges ''pins'' another set ''F'' of edges if every edge in ''F'' intersects some edge in ''K''. Then: * The width of ''H'', denoted w(''H''), is the smallest size of a subset of ''E'' that pins ''E''. * The matching width of ''H'', denoted mw(''H''), is the maximum, over all matchings ''M'' in ''H'', of the minimum size of a subset of ''E'' that pins ''M''. Since ''E'' contains all matchings in ''E'', for all ''H'': w(''H'') ≥ mw(''H''). The width of a hypergraph is used in Hall-type theorems for hypergraphs. Examples Let ''H'' be the hypergraph with vertex set V = and edge set:''E'' = The widths of ''H'' are: * w(''H'') = 2, since ''E'' is pinned e.g. by the set , and cannot be pinned by any smaller set. * mw(''H'') = 1, since every matching can be pinned by a single edge. There are two matchings: is pinned ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected 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 \mathcal(X) \setminus\, where \mathcal(X) is the power set of X. The size of the vertex set is called the ''order of the hypergraph'', and the size of edges set is the ''size of the hypergraph''. A directed hypergraph differs in that its hyperedges are not sets, but ordered pairs of subsets of X, with each pair's first and second entries constituting the tail and head of the hyperedge respectively. While graph edges connect only 2 nodes, hyperedges connect an arbitrary number of nodes. However, it is often desirable to study hypergraphs where all hyperedges have the same card ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Matching In Hypergraphs
In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph. Definition Recall that a hypergraph is a pair , where is a set of vertices and is a set of subsets of called ''hyperedges''. Each hyperedge may contain one or more vertices. A matching in is a subset of , such that every two hyperedges and in have an empty intersection (have no vertex in common). The matching number of a hypergraph is the largest size of a matching in . It is often denoted by . As an example, let be the set Consider a 3-uniform hypergraph on (a hypergraph in which each hyperedge contains exactly 3 vertices). Let be a 3-uniform hypergraph with 4 hyperedges: : Then admits several matchings of size 2, for example: : : However, in any subset of 3 hyperedges, at least two of them intersect, so there is no matching of size 3. Hence, the matching number of is 2. Intersec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hall-type Theorems For Hypergraphs
In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others. Preliminaries Hall's marriage theorem provides a condition guaranteeing that a bipartite graph admits a perfect matching, or - more generally - a matching that saturates all vertices of . The condition involves the number of neighbors of subsets of . Generalizing Hall's theorem to hypergraphs requires a generalization of the concepts of bipartiteness, perfect matching, and neighbors. 1. Bipartiteness: The notion of a bipartiteness can be extended to hypergraphs in many ways (see bipartite hypergraph). Here we define a hypergraph as bipartite if it is ''exactly 2- colorable'', i.e., its vertices can be 2-colored such that each hyperedge contains exactly one yellow vertex. In other words, can be partitioned into two se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique (graph Theory)
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term ''clique'' comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinf ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Line Graph Of A Hypergraph
In graph theory, particularly in the theory of hypergraphs, the line graph of a hypergraph , denoted , is the graph whose vertex set is the set of the hyperedges of , with two vertices adjacent in when their corresponding hyperedges have a nonempty intersection in . In other words, is the intersection graph of a family of finite sets. It is a generalization of the line graph of a graph. Questions about line graphs of hypergraphs are often generalizations of questions about line graphs of graphs. For instance, a hypergraph whose edges all have size is called . (A 2-uniform hypergraph is a graph). In hypergraph theory, it is often natural to require that hypergraphs be . Every graph is the line graph of some hypergraph, but, given a fixed edge size , not every graph is a line graph of some hypergraph. A main problem is to characterize those that are, for each . A hypergraph is linear if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, no ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Independent Set (graph Theory)
In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of ''G'' and is usually denoted by \alpha(G). The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Domination Number
Domination or dominant may refer to: Society * World domination, which is mainly a conspiracy theory * Colonialism in which one group (usually a nation) invades another region for material gain or to eliminate competition * Chauvinism in which a person or group consider themselves to be superior, and thus entitled to use force to dominate others * Sexual dominance involving individuals in a subset of BDSM behaviour * Hierarchy * Patriarchy Music * Dominant (music), a diatonic scale step and diatonic function in tonal music theory * Dominant seventh chord, a four-note chord consisting of a major triad and a minor seventh * ''Domination'' (Cannonball Adderley album), 1965 * ''Domination'' (Domino album), 2004 * ''Domination'' (Morbid Angel album), 1995 * ''Domination'' (Morifade album), 2004 * "Domination", a song by Band-Maid from ''World Domination'' * " Domination", a song by Pantera from ''Cowboys from Hell'' * "Domination", a song by Symphony X from '' Paradise Lost ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Width (other)
Width is a measure of distance from side to side, measuring across an object at right angles to the length. Width may also refer to: Graph theory * Width of a partial order - the cardinality of a maximum antichain. * Width of a tree decomposition of an undirected graph, one less than the size of the largest vertex-set in the decomposition. * Width of a path decomposition of an undirected graph, one less than the size of the largest set in the decomposition * Width of a branch decomposition of an undirected graph, the maximum number of shared vertices of any pair of subgraphs formed by removing an edge from the tree. * Clique-width of a graph, the minimum number of distinct labels needed to construct ''G'' by operations that create a labeled vertex, form the disjoint union of two labeled graphs, add an edge connecting all pairs of vertices with given labels, or relabel all vertices with a given label. * The width of a graph is an alternative name for the degeneracy of the grap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
