Бидний тухай
Багш ажилтан
$\mathbf{G}=(V, E)$ нь оройн олонлог $\mathbf{V(G)}$ ба ирмэгийн олонлог $\mathbf{E(G)}$ байх энгийн граф бѳгѳѳд $\mathbf{v \in V(G)}$ оройн зэргийг $\mathbf{d_G(v)}$ гэж тэмдэглэе. Хавтгайд ирмэгүүдийг нь оройнуудаас өөр цэгт огтлолцохгүй байхаар дүрсэлж чаддаг бол түүнийг хавтгай граф гэдэг. Ѳгсѳн граф болон түүний гүйцээлт дэх гурвалжны тоонуудын нийлбэрийн хамгийн их утгыг графын оройн болон ирмэгийн тооноос хамааруулан олох асуудлыг Гүүдмен анх дэвшүүлсэн. Энэ нь графын ирмэгүүдийг 2 ѳнгѳѳр будахад ижил ѳнгийн талуудтай гурвалжны тооны хамгийн их утгыг олохтой тэнцүү чанартай бѳгѳѳд графын оройн зэргийн квадратуудын нийлбэрийн хамгийн их утгыг олох асуудал руу хѳтѳлдѳг. 1979 онд Күүк $\mathbf{n}$ оройтой энгийн хавтгай граф $\mathbf{G}$-ийн хувьд$\sum_{v\in V(G)}d(v)^2\leq 2n^2+O(n)$ болохыг харуулсан. Харин 1984 онд Трушински түүний дээд торгон хилийг олж тогтоосон. Энэхүү төсөлдѳѳ бид дээр дурдсан асуудлыг ерѳнхий байдлаар томьёолон судлах болно. Тодруулбал $\mathbf{\alpha \geq 2}$ бодит тооны хувьд бид $\sum_{v \in V(G)} d(v)^{\alpha} $ нийлбэрийн дээд торгон хилийг тогтоож тэнцэлдээ хүрдэг графуудыг бүрэн тодорхойлох болно. Манай арга нь аналитик болон тооцоололтой хослуулснаар хавтгай графуудын хувьд зэргийн нийлбэрийн ерөнхий асуудлыг бүрэн шийдвэрлэхийг зорьж байна. Хосолмол аргаар хавтгай графын оройн зэргүүдийн хувьд асуудлыг ерѳнхий байдлаар томьёолон шийдэх бөгөөд энэ арга нь цаашлаад бусад графын инвариантуудыг судлахад ашиглагдах боломжтой юм.
Let $G=(V, E)$ be a simple graph with vertex set $V(G)$ and edge set $E(G)$. The degree of vertex $v\in V(G)$ is denoted by $d_G(v)$. A connected graph is said to be planar if it can be embedded in the plane so that no two edges intersect at a point other than a vertex. Goodman formulated the problem of determining the best possible upper bound for the sum of the numbers of triangles in a graph and its complement, in terms of the number of vertices and edges, which is equivalent to finding the maximum number of monochromatic triangles in the graph. This problem naturally leads to investigating an upper bound for the sum of the squares of the vertex degrees of graphs. In 1979, Cook proved that $\sum_{v\in V(G)}d(v)^2\leq 2n^2+O(n)$ for a simple planar graph $G$ of order $n$. Later, Truszczynski established the sharp upper bound. In this project, we consider the general case in which the powers of the vertex degrees are real numbers. More precisely, for a real number $\alpha\geq 2$, we will obtain a sharp upper bound on $\sum_{v \in V(G)} d(v)^{\alpha} $ and characterize all graphs for which the bound is attained. Our method, which combines rigorous mathematical proof with algorithmic construction and computation, aims to fully solve the generalized degree-power sum problem for planar graphs. Furthermore, this hybrid approach may lead to analogous solutions for other graph invariants in extremal graph theory.
Түлхүүр үгс:Граф нь ѳгѳгдлийн харилцан хамаарал, хэв шинжийг танихад хүчтэй арга болох нь хэдийнээ батлагдчихсан билээ. Бидний судалгаа ѳгѳгдлийн харилцан холбоо хамаарлыг илэрхийлэхэд графын бүтцийг ашиглахад чиглэнэ. Энэ хүрээнд алгебрлаг графын анализ, графын алгоритм, графт суурилсан хэв шинжийн таних техник, сийрэг матрицын декомпозици зэрэг багтана. БНСУ-ын Sungkyunkwan Их Сургуулийн судлаачтай хамтран энэ сэдэв дээр ажиллах юм. Улмаар энэ судалгааны ажил нь Монгол Улсад судалгааны чадавхийг хѳгжүүлэх тэр дундаа ѳгѳгдлийн шинжлэх ухааныг хѳгжүүлэхэд тодорхой хувь нэмэр болно.
Graphs have been proven to be a powerful representation of data relations and have been used in many pattern recognition. We shall focus our attention on methods employing graph structures in order to express data relationships. It covers the following topics: algebraic graph analysis, graph algorithm, graph-based pattern recognition and sparse matrix decomposition factorization. I shall collaborate with the professors of Sungkyunkwan University on the topics. This study will contribute to the development of building research capacity in Mongolia – particularly in its focus on data science.
Түлхүүр үгс:
