Гиперграфиктер – графтардың математикалық кеңейтілмі. Қабырғалар кез келген сандағы төбелерді қосады. Теория, анықтамалар, реттері мен өлшемдері туралы ақпарат.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Графтар теориясының жалпыламасы
Generalization of graph theory
Математикада гиперграф – графтың жалпыламасы болып табылады, онда қабырға кез келген сандагы төбелермен байланыса алады. Ал, қарапайым графта қабырға дәл екі төбені байланыстырады. Формальды түрде, бағытталған гиперграф – бұл жұп , мұнда – төбелер, түйіндер, нүктелер немесе элементтер деп аталатын элементтер жиыны, ал – осы жиындардың әрқайсысы қабырға немесе гиперқабырға деп аталады; төбелер жиыны оның құйрығы немесе домені ретінде, ал – оның басы немесе кодомені ретінде белгілі. Гиперграфтың реті – бұл жиынындағы төбелер саны. Гиперграфтың мөлшері – бұл оның қабырғаларының саны. Бағытталған гиперграфтағы қабырғаның реті : яғни, оның құйрығындағы төбелер санынан кейін оның басындағы төбелер саны. Жоғарыдағы анықтама бағытталған графтан бағытталған гиперграфқа көшу арқылы әрбір қабырғаның басын немесе құйрығын бір ғана төбе ретінде емес, төбелер жиыны (немесе ) ретінде анықтайды. Граф – бұл осы жиындардың әрқайсысында бір ғана элемент бар ерекше жағдай. Сондықтан, қабырғалардың ретіне тәуелсіз кез келген стандартты графтар теориялық ұғым гиперграфтар теориясына жалпыланады. Бір анықтама бойынша, бағытталмаған гиперграф – бұл симметриялық қабырғалар жиынына ие бағытталған гиперграф: Егер , онда . Белгілеуді жеңілдету үшін «қос гиперқабырғаларды» жоюға болады, өйткені «бағытталмаған» модификаторы олардың бар екенін нақты көрсетеді: Егер , онда , мұнда дегеніміз ымырасыз түрде. Граф қабырғалары тек 2 төбені байланыстыра алады, ал гиперқабырғалар кез келген сандагы төбелерді байланыстырады. Дегенмен, барлық гиперқабырғалардың бірдей кардиналдығы бар гиперграфтарды зерттеу жиі қажет болады; k-біркелкі гиперграф – бұл барлық гиперқабырғаларының мөлшері k-ға тең гиперграф. (Басқаша айтқанда, мұндай гиперграф – жиынтықтар жиыны, әрбір жиынтық k төбені байланыстыратын гиперқабырға болып табылады). Осылайша, 2-біркелкі гиперграф – граф, 3-біркелкі гиперграф – ретсіз үштіктер жиыны, және т.б. Бағытталмаған гиперграфты жиынтық жүйесі немесе әмбебап жиынтықтан алынған жиынтықтар жиыны деп те атайды. Гиперграфтарды инциденттік құрылымдар ретінде қарастыруға болады. Атап айтқанда, әрбір гиперграфқа сәйкес келетін екі бөлікті «инциденттік граф» немесе «Леви граф» бар, ал керісінше, әрбір екі бөлікті граф гиперграфтың 2 түсті болған кездегі инциденттік графы ретінде қарастырылуы мүмкін, және қай түс класы гиперграф төбелеріне, ал қайсысы гиперграф қабырғаларына сәйкес екендігі көрсетілген. Гиперграфтардың көптеген басқа да атаулары бар. Есептеу геометриясында бағытталмаған гиперграф кейде диапазон кеңістігі деп аталады, ал гиперқабырғалар диапазон деп аталады. Кооперативтік ойын теориясында гиперграфтар қарапайым ойындар (дауыс беру ойындары) деп аталады; бұл ұғым әлеуметтік таңдау теориясындағы проблемаларды шешу үшін қолданылады. Кейбір әдебиеттерде қабырғалар гиперсілтемелер немесе жалғаулар деп аталады. Гиперграфтар жиыны – гиперграф гомоморфизмдері морфизмдер ретінде саналатын категория.
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, a directed hypergraph is a pair , where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain. The order of a hypergraph is the number of vertices in The size of the hypergraph is the number of edges in The order of an edge in a directed hypergraph is : that is, the number of vertices in its tail followed by the number of vertices in its head. The definition above generalizes from a directed graph to a directed hypergraph by defining the head or tail of each edge as a set of vertices ( or ) rather than as a single vertex. A graph is then the special case where each of these sets contains only one element. Hence any standard graph theoretic concept that is independent of the edge orders will generalize to hypergraph theory. Under one definition, an undirected hypergraph is a directed hypergraph which has a symmetric edge set: If then For notational simplicity one can remove the "duplicate" hyperedges since the modifier "undirected" is precisely informing us that they exist: If then where means implicitly in. 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 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. An undirected hypergraph is also called a set system or a family of sets drawn from the universal set. Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, every bipartite graph can be regarded as the incidence graph of a hypergraph when it is 2 colored and it is indicated which color class corresponds to hypergraph vertices and which to hypergraph edges. Hypergraphs have many other names. In computational geometry, an undirected 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. The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
Өрт жиілігі графигі
H гиперграфы екі бөлікті граф BG арқылы мынадай түрде бейнеленеді: X және E жиындары BG-нің бөліктері болып табылады, ал (x1, e1) шеттері H гиперграфындағы x1 төбесі e1 жиекшесіне кірсе ғана байланысты болады.
A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the parts of BG, and (x1, e1) are connected with an edge if and only if vertex x1 is contained in edge e1 in H.
Керісінше, екінші бөлігінде белгілі бөліктері және байланысы жоқ төбелері жоқ кез келген екі бөлікті граф жоғарыда сипатталғандай гиперграфты көрсетеді. Бұл екі бөлікті граф сонымен қатар инциденттік граф деп аталады.
Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.
Жақындық матрицасы
Гиперграфтың көршілес матрицасы графиктің көршілес матрицасымен салыстырыла береді. График жағдайында, көршілес матрица – бұл төбелердің жұптарының арасында жапсарлылықты көрсететін квадрат матрица. Сол сияқты, гиперграф үшін де, жалпы алғанда, нақты салмақтары бар гиперқабырғаларын ескере отырып, көршілес матрицаны анықтауға болады.
A parallel for the adjacency matrix of a hypergraph can be drawn from the adjacency matrix of a graph. In the case of a graph, the adjacency matrix is a square matrix which indicates whether pairs of vertices are adjacent. Likewise, we can define the adjacency matrix for a hypergraph in general where the hyperedges have real weights with
Қосымша жалпылаулар
Гиперграфты жалпылаудың бір мүмкіндігі – шеттердің басқа шеттерге бағытталуына рұқсат ету. Бұл жалпылаудың екі түрі бар. Біреуінде, шеттер тек қана төбелердің жиынтығынан ғана емес, сонымен қатар төбелердің ішкі жиынтықтары, төбелердің ішкі жиынтықтарының ішкі жиынтықтары және т.б. шексіздікке дейін болуы мүмкін. Асылында, әр шет – ағаш немесе бағытталған ациклді графтың ішкі түйіні, ал төбелер – жапырақ түйіндері. Гиперграф – бұл ортақ түйіндері бар ағаштардың жиынтығы (яғни, берілген ішкі түйін немесе жапырақ бірнеше түрлі ағаштарда кездесуі мүмкін). Керісінше, ағаштардың кез келген жиынтығын осы жалпыланған гиперграф ретінде қарастыруға болады. Ағаштар компьютерлік ғылымда және математиканың көптеген салаларында кеңінен қолданылатындықтан, гиперграфтар да табиғи түрде пайда болады деуге болады. Мысалы, бұл жалпылау термин алгебрасының моделі ретінде табиғи түрде туындайды; шеттер терминдерге сәйкес келеді, ал төбелер тұрақтылар немесе айнымалыларға сәйкес келеді. Мұндай гиперграф үшін жиынға жататындық реттілік береді, бірақ бұл реттілік толық рет те, алдын ала рет те емес, себебі ол транзитивті емес. Осы жалпылаудың Леви графигіне сәйкес келетін граф – бағытталған ациклді граф. Мысалы, төбелер жиыны болып, шеттері және болған жалпыланған гиперграфты қарастырайық. Онда және болғанымен, деп айту дұрыс емес. Дегенмен, мұндай гиперграфтар үшін жиынға жататындықтың транзитивті жабылуы толық реттілікке әкеледі және гиперграфты толық реттелген жиынға «жазады». Балама ретінде, шеттер басқа шеттерге бағытталуы мүмкін, шеттер бағытталған, ациклді графтар ретінде реттелген болуының қажеті жоқ. Бұл шеттік циклдары бар графтарға мүмкіндік береді, онда төбелердің болуы міндетті емес. Мысалы, екі шеті және болған, ал төбесі жоқ жалпыланған гиперграфты қарастырайық, сондықтан және . Бұл цикл шексіз рекурсивті болғандықтан, шеттер жиыны негіз аксиомасын бұзады. Атап айтқанда, мұндай гиперграфтар үшін жиынға жататындықтың транзитивті жабылуы жоқ. Мұндай құрылымдар алғашқыда қызық болмаса да, олардың Леви графигінің баламалы жалпылануы енді екі бөлікті емес, жалпы бағытталған граф екенін атап өту арқылы оларды түсіну оңай. Мұндай гиперграфтар үшін жалпыланған инциденттік матрица анықтама бойынша төртбұрышты матрица болып табылады, оның ранкі төбелер мен шеттердің жалпы санына тең. Осылайша, жоғарыдағы мысал үшін инциденттік матрица жай ғана .
One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ad infinitum. In essence, every edge is just an internal node of a tree or directed acyclic graph, and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout computer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of term algebra; edges correspond to terms and vertices correspond to constants or variables. For such a hypergraph, set membership then provides an ordering, but the ordering is neither a partial order nor a preorder, since it is not transitive. The graph corresponding to the Levi graph of this generalization is a directed acyclic graph. Consider, for example, the generalized hypergraph whose vertex set is and whose edges are and Then, although and , it is not true that However, the transitive closure of set membership for such hypergraphs does induce a partial order, and "flattens" the hypergraph into a partially ordered set. Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges and , and zero vertices, so that and As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer bipartite, but is rather just some general directed graph. The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply