论文标题
签名图中的最小和不连接否定集
Minimal and Disjoint Negation Sets in Signed Graphs
论文作者
论文摘要
签名的图是一个图形，其函数为每个边缘分配一个正值或负的标签。圆的迹象是其边缘符号的产物。如果其所有圆都为正，则图是平衡的。一组否定的边缘产生平衡图的边缘是一个否定集。结果：确定否定集是最小，最小值还是唯一最小值的测试；任何两个不连接的否定集都必须是双方的；证明两类的图具有两分的否定集（通常，存在是一个未解决的问题）；我给出了一种算法，该算法找到了包括给定的否定集的最大不交互式否定集。
A signed graph is a graph with a function that assigns a label of positive or negative to each edge. The sign of a circle is the product of the signs of its edges; a graph is balanced if all of its circles are positive. A set of edges whose negation yields a balanced graph is a negation set. Results: tests to determine whether a negation set is minimal, minimum, or the unique minimum; any two disjoint negation sets must be bipartite; two classes of graphs are shown to have bipartite negation sets (in general, existence is an unsolved problem); I give an algorithm which finds a maximum family of disjoint negation sets that includes a given negation set.
