|
Rainbow-independent Set
In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color. Formally, let be a graph, and suppose vertex set is partitioned into subsets , called "colors". A set of vertices is called a rainbow-independent set if it satisfies both the following conditions: * It is an independent set – every two vertices in are not adjacent (there is no edge between them); * It is a rainbow set – contains at most a single vertex from each color . Other terms used in the literature are independent set of representatives, independent transversal, and independent system of representatives. As an example application, consider a faculty with departments, where some faculty members dislike each other. The dean wants to construct a committee with members, one member per department, but without any pair of members who dislike each other. This problem can be presented as finding an ISR in a graph in which the nodes are the fa ... [...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] |
Abstract Simplicial Complex
In combinatorics, an abstract simplicial complex (ASC), often called an abstract complex or just a complex, is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. Lee, John M., Introduction to Topological Manifolds, Springer 2011, , p153 For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles (sets of size 3), their edges (sets of size 2), and their vertices (sets of size 1). In the context of matroids and greedoids, abstract simplicial complexes are also called independence systems. An abstract simplex can be studied algebraically by forming its Stanley–Reisner ring; this sets up a powerful relation between combinatorics and commutative algebra. Definitions A collection of non-empty finite subsets of a set ''S'' is called a set-family. A set-family is called an abstract simplicial c ... [...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] |
Graph Coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Strong Coloring
In graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint) subsets of equal sizes, is a (proper) vertex coloring in which every color appears exactly once in every part. A graph is strongly ''k''-colorable if, for each partition of the vertices into sets of size ''k'', it admits a strong coloring. When the order of the graph ''G'' is not divisible by ''k'', we add isolated vertices to ''G'' just enough to make the order of the new graph ' divisible by ''k''. In that case, a strong coloring of ' minus the previously added isolated vertices is considered a strong coloring of ''G''. The strong chromatic number sχ(''G'') of a graph ''G'' is the least ''k'' such that ''G'' is strongly ''k''-colorable. A graph is strongly ''k''-chromatic if it has strong chromatic number ''k''. Some properties of sχ(''G''): # sχ(''G'') > Δ(''G''). # sχ(''G'') ≤ 3 Δ(''G'') − 1. # Asymptotically, sχ(''G'') ≤ 11 Δ(''G'') / 4 + o(Δ(''G'')). Here, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cycle (graph Theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an ''acyclic graph''. A directed graph without directed cycles is called a ''directed acyclic graph''. A connected graph without cycles is called a ''tree''. Definitions Circuit and cycle * A circuit is a non-empty trail in which the first and last vertices are equal (''closed trail''). : Let be a graph. A circuit is a non-empty trail with a vertex sequence . * A cycle or simple circuit is a circuit in which only the first and last vertices are equal. Directed circuit and directed cycle * A directed circuit is a non-empty directed trail in which the first and last vertices are equal (''closed directed trail''). : Let be a directed graph. A directed circuit is a non-empty directed trail with a vertex sequence ... [...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] |
Rainbow Matching
In the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Definition Given an edge-colored graph , a rainbow matching in is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors. A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges. History Rainbow matchings are of particular interest given their connection to transversals of Latin squares. Denote by the complete bipartite graph on vertices. Every proper -edge coloring of corresponds to a Latin square of order . A rainbow matching then corresponds to a transversal of the Latin square, meaning a selection of positions, one in each row and each column, containing distinct entries. This connection between transversals of Latin squares and rainbow matchings in has inspired additional interest in the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Boolean Satisfiability Problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called ''satisfiable''. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is ''unsatisfiable''. For example, the formula "''a'' AND NOT ''b''" is satisfiable because one can find the values ''a'' = TRUE and ''b'' = FALSE, which make (''a'' AND NOT ''b'') = TRUE. In contrast, "''a'' AND NOT ''a''" is unsatisfiable. SAT is the first problem that was proved to be NP-complete ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
3-dimensional Matching
In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (instead of edges containing 2 vertices in a usual graph). 3-dimensional matching, often abbreviated as 3DM, is also the name of a well-known computational problem: finding a largest 3-dimensional matching in a given hypergraph. 3DM is one of the first problems that were proved to be NP-hard. Definition Let ''X'', ''Y'', and ''Z'' be finite sets, and let ''T'' be a subset of ''X'' × ''Y'' × ''Z''. That is, ''T'' consists of triples (''x'', ''y'', ''z'') such that ''x'' ∈ ''X'', ''y'' ∈ ''Y'', and ''z'' ∈ ''Z''. Now ''M'' ⊆ ''T'' is a 3-dimensional matching if the following holds: for any two distinct triples (''x''1, ''y''1, ''z''1) ∈ ''M'' a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-completeness
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a deter ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chromatic Number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
