Салмақтанған графтар.
Көп есептерде графтардың төбесі мен доғалары туралы қосымша ақпарат қажет болады, мысалы, егер граф қалааралық жолдарды бейнелесе салмақтанған графтар қолданылады.
Айталық SM, SR - таңбалар жиыны болсын. f: M→SM (төбелерді таңбалау), g: R→SR (доғаларды таңбалау) функциялары G= графын таңбалау бөлінуі деп аталады. G= таңбаланған немесе салмақтанған граф деп аталады.
f(a)-a төбесінің салмағы деп, ал g(e) e доғасының салмағы деп аталады. Доға мен төбенің біреуінің ғана таңбалануы жиі кездеседі.
Мысалы: Айталық M={a1, a2, a3, an}, R={[a1a2], [a2 a3], [a1 a4], [a2 a4]};
f:M→C мұндағы, С- қалалар жиыны, g:R→W.
f(a1)=Омск, f(a2)=Новосибирск, f (a3)=Кемерово, f (a4)=Павлодар
g([a1 a2])=681; g([a2 a3])=274, g([a1 a4])=413; g([a2 a4])=589. Таңбалаған графты–белгілі бір қалалар арасындағы ұзындығы көрсетілген автомобиль жолдарының схемасы. Салмақталған графтардағы доғалардың салмағы туралы ақпаратты салмақ матрицасы арқылы кескіндеуге болады. W=(ij) – мұндағы ij – (ai,aj) доғасының салмағы жоқ доғалар әдетте ноль немесе белгісімен белгіленеді. Қарастырылған мысал үшін салмақтылық матрицасының түрі
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAYEAAAB/CAIAAACG1OmuAAAACXBIWXMAAA7EAAAOxQGMMD9aAAAdz0lEQVR4nO2dfVBU193HN5OCCuILaCw7waJItQhjEBMFRxIKaiBIAC1mBApSAo+gDoaq6CAI+hRfijBWIJDFQHiZSqQYQGkMlIBTRQGVAY0oUgsUIUYwqBmJk8nz9Z48t5sFcUV27727v88fO2fv3pez9577Pd/fueec+4sff/xRRhAEIRC/EDoDBEHoNaRBBEEICWkQQRBCQhpEEISQkAYRBCEkpEEEQQgJaRBBEEJCGkQQhJCQBhEEISSkQQRBCAlpEEEQQkIaRBCEkJAGEaLjzp07V69etbGxmT59utB5ITQOaRAhLmpqapKTkx0cHNLS0g4dOvTqq68KnSNCs5AGEeJiYGAAAhQfH29lZdXb20sapPOQBo0ehAwsWMBtg89JkyYJnSNdYNWqVXK53M/Pr6Ojw9jYWOjsEBpHeA3CnXz//v3Zs2cLnZHnA9mOjY3NzMy8du1aXFwclmzfvh0VeHt7++eff+7v70+SNDoyMjKOHz9eUlLS0tJiaGgodHYIjSOwBrEbmAnQvn37hM2M+pSVlaWmplZVVSFdXV0dGRkJK3T69GloUH9//9dffy10BiUMgi+oz9atWwcHB+GGkpOTKyoqSktLOzs7//Of/6ij7ChU8+bNQyXBvo4bN26QQzthHe+OCTURWINycnKMjIygPgYGBhs3bpRK8B8REQGnAyVaxfHBBx/gX6xevVrofOkCOJ+9vb24k+ExoewQnejo6KtXr+bmFqSkpMTHx4+8OTZEcSooKHj99dd37NjR1dW1bds2CwuLTZs2bdiwQXPZRgFmiZCQEORccwfSPQTWoJ07d166dCkrK0vG1VfCZkZ9UKaDg4MhoEj39Q24uLjA+1y8eBH3z9SpUymCeHGYlWCup6GhAcpSXf0FO+HP3BCrQYOSkpLefPNNGWdU33nn3aAgf7YCdA2eCIWN7Zy15WGJsnnB4fgVVDbh12fFla0DAXr8+DG/OVtn6Gr8zvljsT2rtCrqW/OiwBpUUlJ29mztunXrZP9f7Biovm7evCnaHiLQGtTJSCxZsqSjo4NpqKenJz6PHTuGMC00NFTgLOoQuCdLSkpcXJajVKjjlFkU1traivKDxN27d7/77idRaG9vR3yHSmLatGn5+fm4/997771vv/0WK5eXlzPNgr2Fz0U1g6sMJ4Wjv/322xMmTLh+/fq5c+eCgoKQsLe37+7uxlaFhYUQi8TERCsrK0tLyzlz5uzduzc9Pf3Pf/6znZ0djnL+/Hl3d3fIYk1NDVbGOgqFAsUDe2YtXxcuXMChcRRfX194qLCwMBi3qKgoHF2TJ1VECKxBKBxHjx7FhTE1NfXy8oLTdnBwwHK4cdhvXFdhs/c0IiMjYd9mzJgxnQPlBgutra3x6ePjY2trK07plChpaWmVlZVxcXE45+pH69gE6oMEJOPll19mC+fOnQu9wP0fHh6OK/XXv/719u3beXl5qEXc3NzgZaAU0IJ//etf33///fLly3Ep4aegJgivoGinTp366KOPoGKlpaUJCQkyrhJCQUXesAnyxkosygOE5i9/+QtKyKxZs5h9w3Fra2ubm5sDAwOxh+LiYhTyK1eu4E9BelDjjh8/HjcC9Ah7Y2qoJ6ilQahYINi4VEjjJN6/f3+sDo8QfeXKlUigZoChYLcx4969e2N1lDEHVZ9yKWG6yZjHIUSmdBYIgZOTE5zCc92ZfPwFMfrhhx/45RAgGWdaISIoyVOmTDl9+rSMa8eRcZ7rl7/8JVM6qFJLSwvK4a5du/AVWiPjulCyT5gdeCU4KRY6sU3++Mc/4k558OAB1AcGB2n+uAcOHPD29mZlw9nZOTk5mR0RfwoCxLwblGvZsmXPbPPSMZ6tQTg7CxcuxGU4e/asjHt0qhL9viD8U3kV74DCMVaHICTN80YlrCBZWv7kmMzMzIyM/tu2AvnAbY+wDhGZiYmJjCtpsDmwMIjC5HJ5T0+PjBMjVLevvfYaVKaqqgZyhg2xDsSls7Pz1q0uthMZZ4X4nVdXVxsbG0+cOLG/v//y5ctwcPBQ7CcIE7wVSyMkxGdjYyOfJQR3Mk71ZFwwqD+BmEwdDYqNjd27dx/fpAfn8vXXXwcHB6O6wNelS5fifOEkfvnll4iQnZycfXxWbd68GRYUnhNWE94S1xXSDve7bt06vTKZhPaBdrDGOBgNpPv6BioqKnDPI+pH0VUocgICAjw8PNra2o4ePXrq1On6+npYGJgd2HAIAdIo8LBdSPz6179G2UYIhg2rq7/AQhifffv29fX14SsCPWyLSArrYLeLFi2CHYYqIQSDscLeIEPHjh1DTmC4mLXBhl5eXoi5pk6dWldXt3//fmQVB4XRwx306NEjLMcNhegP/gs/6UlE/2wNQsDMN+kxEPriHG3atAk1AE40rsHHH39cUFBw+PBhCND8+fMjIiJwWnGxcT3ghHGx4Z5OnDgx8jNL5ecFqCK2bduGyy+Vp/WESECYHMkh4x5fwnqgFkQa/gWfqEqZP4JVQVgEK4TyyTZEghU26AWMP/YD1/MqB0ovlkMssHA9BzaHr8FC1gCE3Zqa4sdJOAp2CymBYGEd/PTWW2+xBD5NTU0RkfX29rI9Hzp0CFEY2wTihQwgLeeQSeox8QuiVnuQStMMzg57/Ozu7o76BLKNqwINgmSgWoCVZf0ysNza2hqnFRWRjGtmHuEQubkFiYlxCKdZJ44wjlH/K0LSsHHz7OYcxeYqXltlJ8q/zuYYugeVUEh5k6cZeeVNhu4Wt8Onn34KH6S8ByZwQ9PKzYv6wLM1CGekuLhY2RnCGSEWQz3g6OiIeiY9PX3t2rVwmHzlIPv5OUV5QlA2QjdoqBUb7oAgDlE0Qja+hwWhb8BNMFuNElVYWKgbLSOom3/1q1+lpaXV1taamZnpSZClJs/WIARWiIy2bt3K+gFD0WEpYVLCw8MhRpAhuCRIDKJZKL07BzRFLp/JTG9zc/ORIx86OLRhfU9Pz2GL1Llz5/g0ih02EfNDMUJzGBkZwS+zVmGUKF9f38TERNRwkhtOqIJuKKmGeLYGQbPhdPLy8qA448YZw90gXIJbtrS0fO211xB/IcTFaocPH4ZwIALHytnZ2TIuAkd52rlzJ0LloKD4hISEvr7h3Q02iY2NZVUf9vDZZ591dHSM7f8kJAHKDCwDqj0mQygVqJ8UCkVqairdxrqKWu1B0B3Wq4IHwsQvGRoh8x0cEIrzv47Q6wH7P3jw4Pr162WcD0KZUzkcoScgxr9w4YK9vT3qtsmTJ6MYoLarq6tDeO7i4pKfn68/Ixj0B+Hn7mBA1JhasU7rK1as0LeWOX0GAf6ePXtOnDiBMrB//372BIrJDQoGHFB9ff35841mZmZwRvrWhU/nEYsG8aDAJSYment7o0SSDOkDiL/6+voWLFiAsOtp7T6s9/nixQ5sioXKykrqaKYziE6DZNxoLBSy8vJy0iAdprGxMTw8vKmpCdZmy5Yt6gRZkKGcnBwXl+Wenp52dnas4z4hdcSoQSiOVVVVrq6uMTExEprYjFAHxNo3btzYtGkTwquQkJCGhobn3UNQkL+Hx4o//OEPMERpaWnUj0zqiFGDGFFRUaGhoWwsiNB5IcYA1rqMy9rR0QHv8yIuZvr06aWlpVlZWWwYIz8VJyFFxKtBkJ7du3f7+vp2d3dTny5JU1NTA6UoKyuTcSPLx2qybdaZHn4ZoRmM1RtvvEHBuxQRrwbJuPGxly9fTk9Pp0chEoWpT15enrm5OZsSbMwPwWb1XrRoEY4SHh7p6vomjTGUFqLWIJCZmYmw39DQkHoMSYvc3IKTJz9rb2+HN8nIyND0Y6yGhgb4rKSkpE8+OapXkxDqAGLXIBk3oNnPz08un8nPH0KIGSgOm+5u5cqVgYGBWpMDHMje3v7IkSMRERH//Oc/6WmGVJCABqEKhaW3s7Pz8FhBDUNiJiEhQaFQzJgxY/Xq1YIM8kIUBukJDg7etm0bsoHMkCESPxLQIBnXMUShyFm4cGFnZ6fQeSFUGRgY2Lx5c3Fx8ZQpU9jwY2FbZFBasrOzBwcHf/Ob3+DrGE49TGgCaWiQjOsVEhsb4+XlVVpaKnReiP8SHh5+9OjRBQsW8O+lEAPML0N9ysrKDAwMfHx8ioqKhM4UMTyS0SBw5coVa2trFHp6h5wYiImJSU5OxhUZw8nFxxzEYnfv3v3tb3/7giM8srKy9uzZ09PTw3aCcK+lpQWufPfu3Rs2bKipqdmxYwf/RjPiuZCSBk2aNAkRPq40vU5XQHDyS0pKoqOjXVxccHuLfyA7ctjQ0IBi4+bmFhISsmvXrucNFbu6uszNzaE4qP/YkoMHD6IEQpjmzp2LX3E2Jk+ebGFhoYHs6z5S0iAZV6319Q289957ubm51A1Ey6C2b21tTU1NNTIyOnLkQ2k9poRPCQ0NjYyMXLFiRVRUFKIz9asxNikotMbS0pIJDdsW0oNwLyMjY9OmLYODDyFS1F17FEhMg2Rcw9BXXzXHxsaq8+Zf4sUZHBysq6sr5LCzs9P0i9s1B4SjqKiIdSMqLy9fvXqt+jIK94cNnZyc+vv7BwYG4K2wE5yQ9vb248ePQ9SSktKoC9vokJ4GybgXCqFOQyGgq65RWNhVWVnZ0tLyxhtviKrVedSs4kDhiY2NOXu2dsuWLerMnH/q1OnLly8bGU2C35k5c6aM67bGih8s+YMHD7BP8Yel4kSSGmRvb7979+7s7GzUSzpwV4gQqI9CoUDNP2HCBGdnZ4QwOnaeIR8Ix1JSUpYvXx4REfHMymzxYgdT00l9fQN8EJeWlsZ+Ym0C7G1CxCiQpAaxl9I1NTX5+fmN/MogYhQEBwefOXNm6tSpQnU11A6wP5mZmbm5BZ98cpQFaCPo7NBXeKt8JRM0aiSpQWAtBzTIxsaGvQiceEG6urqCgoKuX78Om1lUVAQN0lX1UYbNRoSQMyQkxMHBAe6GHrlqGalqELs9GhoaEI5ZWVndvHlT6BxJG0j5jRs3EHbV1NRMmzZNr2p1iE5YWBiCrNjYWLlcfvjwYYk2uksUqWoQz9///nczMzPqMTQ6Ghsbvb29e3p6cAfquZ1E+UFo5unp6evrm52d/Y9//EOvhFhAJK9BKCiPHz82MDAQc29dsTEwMAC/k5CQ0NTUlJiYSI8XeVatWoWChBgfFdvf/vY3GvKqBSSvQQxU4xJtGGKdTbR2uK6uLsStqO0fPXo0uumc9QE2uAwVm6mpKaziuHHjyGVrDh3RIBQaCwuL4OBgaXVcRAh5/Phx7bQ+8FMaGhkZ6cx73DUKDFFZWZmjo6O9vX18fDxNFKshRKpB165de/jwIbvqGRkZ9+7dY/ECqnE2PxaMj8rD0XPnzgUFBWFlCTUoonbVdG5Z2NXS0lJcXDx58uTAwECKvNSHdWiMiYnx9vb29/ffuHEjjRAac8SoQe3t7e+8887vf/97pkEQoLi4OHbnfP/997du3Zo6dWpKSkpYWJhy1YTCgdUQySNBlTwD1fhHH33U3d1ta2ubnJysY/0Mtca+ffuWLl2ampqK0oVySKVrbBGjBp05c66jo+OVV15hX3HVIS4sPXv27MzMTIToWVlZUCKVDXGPcSN3kuRyuZ47Z0R5OBvm5uZr1qyxsbEh9XlB2ESxVVU1KF3bt2+XYsujaBGdBkFfvvqqOSQk5GkroG739fU9fPjwsD3o2DtaoVB6O8cQIi9YHngfhF1DI1Zi1MBfBwX529rOu3DhAmR9zpw5NJ3emCA6DcLNg1to/PjxR48eHTaqWrJkSWtr6/79+yFGQ3+dNGlSSUlJQEBAbm6BtCaXYHR1dbEWB0jJ85oXeB+cHFhIKHh6ejq1XGgCB46VK1cmJibOmDHjwIFDUixmokJ0GsQ6aMTExLD00BWmc/T39+N2HXYPkCF3d/eNG/9Hiq+a4jP8XAIEOQ4NDe3r66M+vtoBHjwnJycjIyM0NLi4+Fh2djY9vB81otMgngkTJrCEgYEB+4Q2wR24ubnhK2qhEW42/AS3PGvWrObmZt0ORqA+ERERPT091NVQ+6CY+fv7v/3227a2tmSIRo1INUj55VDKHaDhDtTsD401X3/99ZSUFJ1sGELYderUaVTCSJP3ERCYbvYaa19f3+rqL+DfdbvO0wQi1aAxAYUDEbuMe1mr0HkZMxobG0+fPp2eno6/NvIk7S+99BI+f/zxR3W+Ei8C34BgZ2enUOTY2s7T88eyz4Uua5CM6z/t6em5bt06qT+cHhgYuHTpUkVFxaeffgr1gQaN3EsFEqOsL/xXllD5qunM6wkw7zt37gwICNi4sbqwsNDe3l5yzZGCoOMaBOk5cuRDNzc36Y5oZR2d8/Ly2tvb5XL5F198oea0PqQv2gehWWlpKUKzqKgoS0vLuLg4qVd+WkDHNUjGTVJ161abl5dXamqqtCbl6urqys7Orq2tNTY2dnR0fK4JVVVsDvM+Mgq+tAIsqrW1dUlJyYYNG5YtW7Z37156ajYCuq9BID4+3tXVFeG6hF62GR4eXllZOX/+fJi4F59QVSX44iWJ0BDz5s3bsWOHk5MTwmd6ajYyeqFBMu7lB0FBQQkJCdAjofMyEteuXQsICOjs7LSwsDh58uTEiRM11Kag3CpEaAj4Vnt7+6VLlxYXF2/c+D9NTU3ScuLaQV80CHcyQvR169YFBgaKsxwg8vLz86uvrw8JCcnPz5fL5aOeV4j3OLzEqMRiFJdpDVxEhGZLliyZO3cuAmp4oqqqKqEzJS70RYNkXJR+4MAB3Oewx6KKz+F9li9f3tPT4+zs3N3d/eJ5G1ZclBeS+mgZXFOEZitWrECIbWBgoFDkUGjGo0caJONkKDs7Oz09XQwR2cDAQElJWWJiXEdHB/Vy1gccHBwaGhrYCI/q6i/i4uLEacm1jH5pECKyoqIiROmGhoYj3/N37twZHBzUUFvMAMesWbNMTU3Xr1+v3Cmc0Hk2cFhYWJw5cyY1NRVhmqhcufbRLw2ScaMN8/Pz3dzcEJmP0M1PQ8UC0nb16tW0tLSamhoy5PpMZ2dne3u7o6Pj4sWL33//fdSLevsaD73TIBn3tAKxz/bt27U5IV5XV1dZWVlFRcWVK1fmz59/48YNvS1zBAPVYW9vb1ZWVkREhIeHhw705h8d+qhBMm5uxtbW1vDwcC0MJWMjvM6dOyfjWgQOHDhAwxoJnrCwMGdn55SUFARogYGBoaGh+haa6akGgZycHAMDA09PT825IXgfVHFtbW1z5sxxd3dfs2aNvhUvQh1QJx08ePDSpUvR0dEKheLkyZN6VUvprwaBurq6JUuWaGKOIYRdSUlJiPldXV0zMjJsbGxIfYgRQGCOQKyoqAhlxs7ODjWW/kwUq9cahMgIEdncuXPHUIYQeSHEY+8v9fHxeZGuhoS+MZsDpbG2thYmPSQk5HnbCmbMmLF48WJzc3MJzVej1xok4646lGL58uWof15wV2wiKyRiY2PF1g2SkBDzOFA1Jicnm5iYlJeXq9lWbWVlhc/8/HwzMzMJtXDruwbJuDmGbDhG/cKWrKysXbt2fffdd/SGcmKseJMDEb2bmxuqybS0tGfWajdv3sRncHDw+PHjtZLHsYE06Ak1NTULFy583ldxsM4+KCK45KiywsLCNJdDQj/ZsWPH2rVrPT09oUf79+8fuYZDgbS1te3t7S0oKNBaDl8c0qAnoIZJT09PTU318VmlfvMNrvfEiRN1ftp8Qlhmz56Nqg6GKDQ0dP369b/73e+eNlHsu+++a2ho2NjYuGDBgrNnz8o4M3Xt2jWEZmJuGSAN+gnUMC0tLQEBASO8mQv1TF1d3cWLF8vKyuRyuUKhoMiL0A47OFxdXeFxEPiz15yprAPdCQ8Pz8rKOnHiRF5eHgQIBr+wsBA/iXkeNdKg/4Jr7OfnFxsbm5OTo/ITU5/i4uLr169PmzatqKiIRhsS2qeqqgpF0d3dHelNm7Z4eKxQURb+cRgbDmlvb4/P5ORkref0OSAN+hmJiYnbtm2D742MjGRB2cDAwNatW9va2pBes2YNvbyFEBaITkNDA8zO/v3/W1x8LDo6eoTnX6wMe3p6ogYVrWcnDfoZ0BcbG5u4uDhEW8HBwbdv3z527NicOXOgPi4uLqQ+hEhgIzxg2AMCAiIiIkaYBILN5RgaGkoaJA0aGxsrKyuRqK+vb25unjt3LuJqa2tr6mdIiA3UiDt37kRNCeduYmLy5ZdfDm0hys0tgFcyNTXdvn27IJlUB9Kgn/HgwYPe3l6Wvn//vrCZIYiRmcSRn5//zTffODo69vX1qbzDysdnlavrk0hNzG86Iw36GTCuuKKInx89eiR0XghCLZgSoe6E63FycoKFX7BgQUNDA/+T0Bl8BqRBP8HmNmRDB1UcEAK08vJyJF555RV8vvzyy3fv3kUC11sq3eEJfeDkyc8gQEg0NTWhcLIuQuKHNOgnRqgxjI2NIUMVFRWJiYly+UxT00mRkZHR0dHsZfYEIRIk9Po8ZUiDns28efMQnV25ckX5XYPu7u5YfufOHYVCMWXKFH9/f0gYmyzx3//+N36FRcKvJSUlzDRBvL76qplNHR0TEzN58uTAwEAWpWOTlpYWts7g4MOwsLCMjIx79+7xK8i4DkrY1e3bt8UwGz9BjCGkQWrxww8/fM/BL0HgBl2A0Cxbtgxfz58/n5OTc+rUqc2bN3d3d8vlcjZ+1cPDY8+ePZCwhIQE9nB00aJFDg4OS5cudXR0PHHiBNIQr2+//Ray5ebmBsHy8/Nrb2+HEiGRn5+PTd5///3a2trm5mbIkIQ8NkGoA2nQ6Jk+fToMi729/datW69fvw5V4pfjE9YGogMjY2lpaW1t3d/fv3DhQsR0iNVZe2F5eXlWVlZmZqaFhQVsEevSCj1CoIclsF2dnZ3YCiIF+8NsF36Ki4tLSkqiFwEROgNp0HNgaGiossTKyupPf/pTYWGhi4sL35wUHBwcEhJia2ursjJWePDgwdDdfv7553A3/OZsxob09HQTExNjY2MsQazH70Fa0zIQxDMhDXoC/Ag+zc3Nn9aX9N69ezLufSzKw8QQMUEvQkNDYU8QK3V1dSFkk3EzVcPvvPXWW1gBnggR3MOHD/EJowRDxG/b1tbm7OyM9OXLlyFhiOzYT15eXojmoEFRUVE3btxgnbOxMjb/5ptvHj16NFTdCEK6kAY9sS3FxcVHjnzo6+ublpY2dBqgsrKyvLw89lrEoqKiDz74YObMmSwgglIkJCSsXr16woQJWAf7wU/h4eHNzc0QpqtXr0ZHR8fHx8P+ILyKiIiAirW2trIJNyFA+MnPzw+ykpKSgoALxgfbYp+QtosXLy5btoyNfp42bVp9fb2Pjw/iO4UiR7Sd7glt8tJLL7EEe3M3+yrFt3iTBskKCgpwewcF+YeGBh87dmyoBq3i4L+qPAFlP7EGmqHNNKzpR8bNq8AS7K1SLA3rlJiYyA9Dg3tiz8LYhHg8MEH+/v5DR/MT+gzkBrrDC5AU1YdBGiR7/Pgx4iCYHRnXFUibh1bpQe/g4FBXV6eyDoRpypQpfX19yCE5IEL3IA16wrvvviuS23toP0nEcYj7kLh1q0uIHBFiZ1gTpByaKUdtI0dw/Nenba78deiGslEFg6RBP70OBWFUXFyc0HkZBn44CA0LIYbyNAFSjtGUpYehEsHxCbam8nLZz4WG35vyhsp5GEVUSBr0ZFroS5cu5eYWWFtbI+Hk5FRUVMSipJqaGhoRRogZFQngURGdpzHsauqIyBg2gZMGPZkfMyEh4datNihOenq6p6cnP4TC19dXZTIEghAbw8rQUHXgVxs2mBrFQWVj1BZOGvQEfhAWn4AesRcWEoR0UVMjVFbT8lM20qDh+fjjj+vq6ry9vYXOCEEMD7MzKi0+ys06suFakflth27Fo06b9LCHG7ordSANGobg4ODVq1c7ODgoD1IlCFExcvCl/JVP85LxtK1G3nyETV7EN5EGDUNBQUFFRQUSfX190CPqHEgQmoM0aBj4dmgTExMSIEJ/UI7vtHZQ0qCROHDggNBZIAjtIciAD9KgkdiwYYPQWSAIHYc0iCAIISENIghCSEiDCIIQEtIggiCEhDSIIAghIQ0iCEJISIMIghAS0iCCIISENIggCCEhDSIIQkhIgwiCEBLSIIIghIQ0iCAIISENIghCSP4PpGRuu5qLgaIAAAAASUVORK5CYII=)
Графтарға қолданылатын амалдар. Графқа төбе қосу.
G= графына а төбесін қосқаннан <М {a}, R> графы құралады.
Графқа доға қосу операциясының нәтижесінде <М {(a,b)}, R {(a,b)}> графы құрылады.
Графтан доға алу–R доғалар жиынынан (a,b) жұбы алынады.
Графтан төбе алу операциясының нәтижесінде. G графынан а төбесі оған инцидентті доғалармен бірге алынады деп айтады.
Графтың a,b төбелерін теңестіру деп графтан a,b төбелерін алып тастап мына тәртіппен төбе мен қабырға қосу: жаңа а1 төбесі мен (а1, с), егер (а, с) R немесе (b, с) R және (с, а1) доғасын егер (с, а) R немесе (с, b) R болса:<(M\{a,b}) {a1}, (R\{(с, d)│c=a немесе d=a, немесе c=b, немесе d=b}) {(a1,c)│(a, c) R, немесе (b, c) R} {(c, a1)│(c, a)R, немесе (c, b) R}).
Алынған граф G графынан a,b төбелерін теңестіргеннен алынды делінеді.
a,b төбелері доғамен қосылса, төбелерді теңестіру a,b доғасын созғаннан алынады дейді. Мысалдар: Берілген=<{1,2,3,4},{[1,2],[2,3],,(3,4)}> графынан суреттегі G1-G6 графтары қандай операциялармен алынды?
G графына 5 төбені қосқаннан G1 графы алынды.
G графына (3,1)–доғасын қосқаннан G2 графы алынды.
G графына (3,2) доғасы алынады G3 графы алынды.
G графына 2 – төбені алғаннан G4 графы алынды.
G графының (1,4) төбелерін теңестіргеннен G5 графы алынды.
G графының (2,3) доғасын қысқаннан G6 графы алынды.
=2\R IdМ> графы ілгексіз G= графының толықтырушы графы деп аталады.
Мысал: Айталық, G1=1,R1>, G2=2,R2> графтары берілсін.
G= ; =2 \R IdМ>
Достарыңызбен бөлісу: |