有向圖
- 串并有向圖的判定算法及應(yīng)用實例
解決思路，串并有向圖經(jīng)常作為約束條件使用，其應(yīng)用范圍十分廣泛。例如：成龍等人[7]提出的關(guān)于1｜sp_Graph｜∑Wj(1-e-rcj)問題的最優(yōu)算法；閆楊等人[8]研究的1｜sp_Graph｜WjCj問題；高文軍等人[9]討論工件間具有串并有向圖約束的preempt-repeat 模型，則是用LAWLER EL[10]提出的任務(wù)合并和由底向上搜索分解樹的方法求解；陳昊[11]、張大宇[12]、黃玉[13]、萬龍[14]這些學(xué)者在相關(guān)研究中也均涉及串并有
科技資訊 2023年21期2023-11-22
- 有向圖的頂點加權(quán)zeta 函數(shù)
0]逐步定義了有向圖的Ihara zeta 函數(shù)、有向圖和無向圖的邊加權(quán)Ihara zeta 函數(shù)，并給出了這些zeta 函數(shù)的行列式表達(dá)式。2007年，Horton[11]討論了有向圖的Ihara zeta 函數(shù)的相關(guān)性質(zhì)。2019 年，Konno 等[12]通過給無向圖的頂點加權(quán)，定義了圖G的一個新的加權(quán)Ihara zeta 函數(shù)，并給出了它的行列式表達(dá)式。2021 年，Zhu[13]定義了圖G的一個頂點加權(quán)Bartholdi zeta 函數(shù)，并給出其
上海理工大學(xué)學(xué)報 2022年5期2022-11-24
- 局部外競賽圖上的二次外鄰
V，A）是一個有向圖，其中V（D）和A（D）分別表示D的頂點集和弧集。對于任意的頂點x，y∈V（D），如果（x，y）∈A（D），則稱（x，y）是D的一條弧，y稱為x的外鄰點，x稱為y的內(nèi)鄰點。設(shè)H是D的任意一個頂點子集，也可用H表示其在D上的導(dǎo)出子圖，對D的任意的一個頂點x，它在H上的內(nèi)鄰點集和外鄰點集分別記為：同樣，對任何頂點子集S?V（D），它在H上的內(nèi)鄰點集和外鄰點集記為：分別為x在H上的入度和出度。x在H上的二次外鄰點集和二次內(nèi)鄰點集記為：記d++
山西大學(xué)學(xué)報（自然科學(xué)版） 2022年4期2022-08-15
- 廣義棱柱中的超歐拉有向圖
有限無環(huán)的圖和有向圖，沒有特殊說明的話，圖指的是無向圖。文中未定義的符號和術(shù)語，無向圖參見文獻(xiàn)［1］，有向圖參見文獻(xiàn)［2］。定理1[9]設(shè)G是n個頂點的連通圖。如果G∈F，那么對于任意的 α∈Sn，α(G)都是超歐拉圖。一個有向圖稱為是歐拉有向圖，是指它有一條包含所有弧的閉跡。如果一個有向圖D包含一個生成歐拉子有向圖，則稱D是超歐拉有向圖。文獻(xiàn)［15］和［16］給出了若干有向圖是超歐拉圖的充分條件。受到廣義棱柱較多的研究成果及應(yīng)用、以及有向圖的超歐拉性的相
山西大學(xué)學(xué)報（自然科學(xué)版） 2022年1期2022-03-08
- 極大限制弧連通有向圖的度條件
］。本文討論的有向圖都是有限的且沒有環(huán)和多重弧。對有向圖D，用V=V(D)和A=A(D)分別表示D的頂點集和弧集。對有向圖D中的一個頂點v，它的外鄰域為N+(v)={u∈V(D)：vu∈A(D)}，出度為D的最小出度是點v的內(nèi)鄰域N－(v)，入度d－(v)和D的最小入度δ－(D)可類似定義。頂點v的度定義為d(v)=min {d+(v)，d－(v)}，有 向 圖D的 最 小 度 定 義 為δ(D)=min {d(v)：v∈V(D)}=min {δ+(D)，
山西大學(xué)學(xué)報（自然科學(xué)版） 2021年4期2021-08-31
- m-步p-競爭模糊圖
言本文中涉及的有向圖是無環(huán)、無多重弧的簡單有向圖。模糊集［3］是描述不清晰、不確定和界限模糊事物的一種重要數(shù)學(xué)結(jié)構(gòu)。1987 年Bhattacharga 提出了模糊圖［4］的概念。隨后雙極模糊圖［5］、直覺模糊圖［6］、模糊平面圖［7］等概念被相繼提出。將模糊圖與競爭圖的概念相結(jié)合，提出了雙極模糊競爭圖［8］、直覺模糊競爭圖［9］、雙極單值中智模糊競爭圖［10］等概 念。2013 年，Samanta 和Pal 介 紹 了p-競 爭 模 糊圖［11］。201
山西大學(xué)學(xué)報（自然科學(xué)版） 2021年3期2021-08-31
- 有向圖的Roman k-控制
006)設(shè)S是有向圖D的頂點集V的一個子集,如果N+[S]=V,則稱S是有向圖D的一個控制集[1].有向圖D中最小控制集的階稱為D的控制數(shù),記作γ(D)[1].設(shè)k是一個正整數(shù),S是有向圖D中V的一個頂點子集,如果|N-(v)∩S|≥k對于每個v∈VS均成立,則稱S是有向圖D中的一個k-控制集.有向圖D中最小k-控制集的階稱為k-控制數(shù),記作γk(D).有向圖D中的一個階數(shù)最小的k-控制集叫做γk(D)-集.有向圖D中的一個階數(shù)最小的1-控制集叫做γ(D)
云南民族大學(xué)學(xué)報（自然科學(xué)版） 2021年3期2021-06-24
- 圍長為5的3-正則有向圖的不交圈
為g的3-正則有向圖不含不同長度的不交圈。g=3和g=4的情況在2017年和2020年分別被證明。本文主要證明了圍長為5的3-正則有向圖具有兩個不同長度的不交圈的存在性問題，給出了幾個充分條件。關(guān)鍵詞：3-正則有向圖;圍長;不交圈中圖分類號：O175.5 ?文獻(xiàn)標(biāo)識碼：A ?文章編號：1673-260X（2021）04-0001-051 引言與預(yù)備知識在整篇文章中，只考慮有限的簡單的有向圖，特殊標(biāo)注的地方除外。本文提到的有向圖的其他定義可以參考J. Ban
赤峰學(xué)院學(xué)報·自然科學(xué)版 2021年4期2021-06-24
- 準(zhǔn)傳遞定向圖上的Seymour點
次鄰域的問題是有向圖理論中最有趣,最具挑戰(zhàn)性的問題之一.這里,定向圖是指沒有2圈的有向圖.本文涉及到的有向圖是無環(huán),無平行邊的簡單有向圖,相關(guān)的術(shù)語和符號參看下一小節(jié)以及文獻(xiàn)[1].猜想1.1[2](Seymour二次鄰域猜想) 在定向圖D中,總可以找到一個頂點x,這個頂點的二次外鄰域至少和它的外鄰域一樣大,即d+(x)6d++(x).根據(jù)文獻(xiàn)[3],這樣的頂點x稱為Seymour點.值得注意的是,猜想1.1只適用于定向圖,并不適用于一般的包含2圈的有向圖
高校應(yīng)用數(shù)學(xué)學(xué)報A輯 2020年2期2020-07-07
- 關(guān)于有向圖弧連通度的一些結(jié)果
設(shè)(X,Y)為有向圖D的任一滿足|(X,Y)|≤δ-1的弧割，則|X|≥max{δ++1,ξ++2}且|Y|≥max{δ-+1,ξ-+2}.kp(p-1)+k(|X|-p)(p-1)+λ=k(p-1)|X|+λ故證明 令X,Y,D′,D″,J與定理1.4證明中的相同.故由|Y|≥a，故可以同樣的方法在D″中定義Ci″(1≤i≤J)和Ctj″(j=1,2,…,k)同理可證因此有2 結(jié)語本文給出了有向圖弧連通度與圖的團(tuán)數(shù)、圖的度序列之間的關(guān)系，推論給出了有向圖
太原師范學(xué)院學(xué)報(自然科學(xué)版) 2019年4期2020-01-07
- 一類特殊三色有向圖的本原條件和指數(shù)上界
、黃弧和藍(lán)弧的有向圖，則稱D是一個三色有向圖。若D中每一對頂點(i,j)都存在從i到j(luò)的途徑，則稱三色有向圖D是強(qiáng)連通的，給定D中的一條途徑ω，用r(ω)、y(ω)和b(ω)分別表示ω中紅弧、黃弧和藍(lán)弧的條數(shù)，稱ω為一條(r(ω),y(ω),b(ω))-途徑，ω的分解為向量(r(ω),y(ω),b(ω))或(r(ω),y(ω),b(ω))T[1]。一個三色有向圖D是本原的，當(dāng)且僅當(dāng)存在非負(fù)整數(shù)h、k和v，且h+k+v>0，使得D中的每一對頂點(i,j)都存
長江大學(xué)學(xué)報(自科版) 2019年7期2019-07-22
- 依賴于團(tuán)數(shù)的有向圖弧連通度的下界
)0 引言一個有向圖D,V=V(D)和A=A(D)分別是有向圖D的頂點集和弧集.有向圖D的階是D中頂點的數(shù)目，常用n=|V(D)·表示，有向圖D的規(guī)模是D中弧的數(shù)目，常用m=|A(D)·表示.如果xy是D的一條弧，稱x控制y,且稱x為弧的尾，y為弧的頭.設(shè)X和Y是有向圖D的頂點子集，定義(X，Y)={xy∈A(D)∶x∈X，y∈Y}為D的弧子集，包含了有向圖D中全體尾在X、頭在Y中的弧.定義集合N+(v)={u∈V(D)-v∶vu∈A(D)},N-(v)=
太原師范學(xué)院學(xué)報(自然科學(xué)版) 2018年1期2018-08-06
- 有限自動機(jī)可識別語言的基數(shù)
動機(jī)可看作一個有向圖。利用圖的鄰接矩陣可研究圖中的路及圖中任意兩個結(jié)點間的可達(dá)性等問題。對于一個字符集Σ上的有限自動機(jī)M，一個字w∈Σ*（Σ*是Σ上有限字符串的集合）可被M識別當(dāng)且僅當(dāng)在w的作用下，按照狀態(tài)轉(zhuǎn)移函數(shù)，自動機(jī)由初始狀態(tài)到達(dá)終止?fàn)顟B(tài)。這表明，如果把自動機(jī)看作一個有向圖，可利用其鄰接矩陣，研究該自動機(jī)可識別的語言。因此，本文利用有向圖的鄰接矩陣研究有限自動機(jī)可識別語言的基數(shù)問題。2 有向圖的鄰接矩陣簡單回顧有向圖及其鄰接矩陣的相關(guān)知識，詳見文獻(xiàn)[
計算機(jī)工程與應(yīng)用 2018年15期2018-08-01
- 超歐拉和雙有向跡的強(qiáng)積有向圖
下面介紹了強(qiáng)積有向圖的定義.定義1令D1=(V1,A1)和D2=(V2,A2)是2個有向圖,V1={u1,u2,…,un1},V2={v1,v2,…,vn2},則D1和D2的強(qiáng)積有向圖定義如下:強(qiáng)積有向圖記作D1?D2,其點集為V1×V2,任意2個不同的點(ui,vj)和(us,vt),若((ui,vj),(us,vt))∈A(D1?D2)當(dāng)且僅當(dāng)以下3個條件之一成立:1)ui=us且(vj,vt)∈A2;2)vj=vt且(ui,us)∈A1;3) (ui
四川師范大學(xué)學(xué)報（自然科學(xué)版） 2018年4期2018-07-04
- 特殊雙圈雙色有向圖的本原指數(shù)界
n個頂點的伴隨有向圖D(A,B)存在一一對應(yīng)關(guān)系[1]，即(A,B)中元素的符號和D(A,B)中弧存在與否相對應(yīng)。例如：設(shè)矩陣A=(aij)，B=(bij)，若aij>0(bij>0)，則表示D(A,B)中從頂點i到頂點j存在一條紅弧(藍(lán)弧)；相反，不存在紅弧(藍(lán)弧)。只含紅弧和藍(lán)弧的有向圖D，稱為一個雙色有向圖[2]。若記exp(A,B)為非負(fù)本原矩陣對(A,B)的本原指數(shù)，exp(D(A,B))為非負(fù)本原矩陣對(A,B)所對應(yīng)的伴隨有向圖(即雙色有向圖
陜西理工大學(xué)學(xué)報(自然科學(xué)版) 2018年3期2018-06-19
- 有向圖的無符號拉普拉斯譜半徑的新上下界
D(G).因為有向圖G是一個連通圖，則有向圖G的無符號拉普拉斯矩陣Q(G)為一個非負(fù)不可約的矩陣[1].設(shè)無符號拉普拉斯矩陣Q(G)的特征值由大到小排列為q1(G)≥q2(G)≥…≥qn(G)，則稱q1(G)為有向圖G的無符號拉普拉斯譜半徑.對于無向圖G的無符號拉普拉斯譜半徑的研究已經(jīng)取得了很多不錯的成果.最早，Cvetkovic等[1]給出了圖G的無符號拉普拉斯矩陣的定義,文獻(xiàn)[2-3]給出了圖G的無符號拉普拉斯譜半徑與拉普拉斯譜半徑之間的大小關(guān)系,但目
四川師范大學(xué)學(xué)報（自然科學(xué)版） 2018年3期2018-06-04
- 具有禁止子圖的有向圖是超歐拉有向圖的條件
].禁止誘導(dǎo)子有向圖一直是被廣泛研究的話題.給定一個有向圖K和一個有向圖D,如果對于D的任意一個子圖H,若滿足H≌K,則|A(D〈V(H)〉)|>|A(H)|+1,則稱D不含K子圖.一直在被深入研究的是成為哈密頓的充分條件是不含K1,3子圖,可以參考[10].1 主要結(jié)論如果D是非哈密爾頓的,但是強(qiáng)連通的,則在D中存在至少一個S-路或S-圈.A.Kemnitz和 B.Greger給出了定理1中的結(jié)論.定理1[10]如果R是一個至少有3個點的定向圖且不含圖1
商丘師范學(xué)院學(xué)報 2018年3期2018-03-20
- 關(guān)于超歐拉的冪有向圖
關(guān)于超歐拉的冪有向圖崔秋月，劉 娟*(新疆師范大學(xué)，新疆 烏魯木齊 830017)如果一個有向圖D包含一個生成有向閉跡，則稱D是超歐拉有向圖。研究關(guān)于一個強(qiáng)連通有向圖或一個強(qiáng)連通的有向圖類，使之在經(jīng)過p次冪有向圖的運算后成為超歐拉有向圖的充分條件：有向圖D包含一個有向圈的集合 Γ=｛S1，S1，…，Sn｝且滿足 V（D）=Usi∈ΓV(Si)，D 的平方圖是超歐拉有向圖的充分條件。對于s,t圖類中的強(qiáng)連通有向圖，當(dāng)s是奇數(shù)時，則對于任意的是超歐拉有向圖；當(dāng)
廊坊師范學(xué)院學(xué)報(自然科學(xué)版) 2017年3期2017-10-11
- 關(guān)于路立方圖的一個充要條件
38000)在有向圖中,哈密爾頓圖一定是強(qiáng)連通圖,但強(qiáng)連通圖不一定是哈密爾頓圖，本文證明了一類具有偶數(shù)階的路立方圖的任何定向,通過推點運算,可推成哈密爾頓有向圖，當(dāng)且僅當(dāng)可推成強(qiáng)連通有向圖.強(qiáng)連通；哈密爾頓；推點1 引言文中未提及的符號和術(shù)語,參見[1].關(guān)于路圖的立方圖的研究,主要有以下結(jié)果.關(guān)于哈密爾頓可推性與強(qiáng)連通可推性的等價性,Klostermeyer已經(jīng)證明如下結(jié)論.定理4[5]圈圖的平方圖的任何定向,當(dāng)且僅當(dāng)可推成哈密爾頓圖,一定可推成強(qiáng)連通有
黃岡師范學(xué)院學(xué)報 2017年3期2017-06-21
- 圓有向圖的(1,2)步競爭圖中存在哈密爾頓圈的條件
30000)圓有向圖的(1,2)步競爭圖中存在哈密爾頓圈的條件崔 建1，葉 旺2(1.山西醫(yī)科大學(xué)汾陽學(xué)院 基礎(chǔ)醫(yī)學(xué)部，山西 呂梁 032200; 2.山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，太原 030000)針對圓有向圖的(1,2)步競爭圖的結(jié)構(gòu)，提出了競爭圖中是否存在哈密爾頓圈；通過特殊到一般的方法得到如下結(jié)論：對于階數(shù)n(n≥5)的強(qiáng)連通圓有向圖的(1,2)步競爭圖中存在哈密爾頓圈，而其余情形的圓有向圖的(1,2)步競爭圖中則不存在哈密爾頓圈。圓有向圖；(1,2)
重慶工商大學(xué)學(xué)報（自然科學(xué)版） 2017年6期2017-03-11
- The Twin Domination Number of Lexicographic Product of Digraphs
731003)有向圖字典式積的雙控制數(shù)馬紅霞，劉 娟*(新疆師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，中國 烏魯木齊 830054)令γ*(D)表示有向圖D的雙控制數(shù)，Dm[Dn]表示有向圖Dm和Dn的字典式積，其中Dm,Dn的階數(shù)m,n分別大于等于2.本文首先給出Dm[Dn]的雙控制數(shù)的上下界，然后確定如下有向圖的雙控制數(shù)的確切值：Dm[Kn];Km[Dn];Km1,m2,…,mt[Dn];Cm[Dn];Pm[Cn]及Pm[Pn].雙控制數(shù)；字典式積；有向圖10.7612/
湖南師范大學(xué)自然科學(xué)學(xué)報 2016年6期2016-12-23
- 恰含1個n圈和2個s圈的本原有向圖的scrambling指數(shù)
2個s圈的本原有向圖的scrambling指數(shù)宋卓蓉，高玉斌 （中北大學(xué) 數(shù)學(xué)系，太原 030051）摘要：在圖Ds，n的基礎(chǔ)上，增加1個s長圈.研究含有1個n長圈和2個s長圈（2個s長圈有公共頂點）的本原有向圖.通過分析圖中每個點經(jīng)過t長途徑所到達(dá)的點的集合及點的個數(shù)，得出此類本原有向圖的scrambling指數(shù).關(guān)鍵詞：本原有向圖；scrambling指數(shù)；圈1 引言與預(yù)備知識2009年，Akelbek等［1］將本原有向圖本原指數(shù)的概念進(jìn)行了推廣，提出
天津師范大學(xué)學(xué)報（自然科學(xué)版） 2016年1期2016-09-07
- 多部競賽圖中包含在一些圈中的頂點
為無重弧和環(huán)的有向圖。一個多部競賽圖或c-部競賽圖是一個完全c-部圖的定向。設(shè)D是一個有向圖，我們用V（D）表示它的頂點集。若xy是D中的一條弧，我們說x控制y，記為x→y。對于V（D）的兩個子集 X和Y，若X的每個頂點控制Y的任意頂點，我們說X控制Y，記為X→Y。稱一個有向圖D是強(qiáng)聯(lián)通的，若對于D中任意兩頂點u和v，都存在一條從u到v的路。有向圖D的一個圈稱為哈密爾頓的，若它包含D所有的頂點。參考文獻(xiàn)[1]Bang-Jensen J，Gutin G. D
電子技術(shù)與軟件工程 2016年8期2016-07-10
- 一類特殊本原有向圖的m－competition指數(shù)
）一類特殊本原有向圖的m－competition指數(shù)李林倩1,方 煒2（1.山西農(nóng)業(yè)大學(xué)信息學(xué)院,山西晉中030800；2.中北大學(xué)儀器與電子學(xué)院,山西太原030051）對一類含有兩種不同圈長的本原有向圖的m－competition指數(shù)進(jìn)行了研究,根據(jù)圖論知識,通過分析本原有向圖D與本原有向圖Dn－4,Dn－2之間的關(guān)系,結(jié)合本原有向圖m－competition指數(shù)的定義,利用集合的運算給出了此類圖的m－competition指數(shù).本原有向圖；途徑；m－c
太原師范學(xué)院學(xué)報(自然科學(xué)版) 2016年4期2016-02-24
- 一個含四個圈的本原有向圖的m-competition指數(shù)
含四個圈的本原有向圖的m-competition指數(shù)宋卓蓉，高玉斌(中北大學(xué)數(shù)學(xué)系, 山西太原030051)[摘要]對于n階本原有向圖D中任意頂點u和v,若都存在m(1≤m≤n)個不同的頂點v1,v2,…,vm∈V(D), 使得成立，則稱最小正整數(shù)k為本原有向圖D的m-competition指數(shù). 本文研究了一類含有一個n長圈、三個n-2長圈的本原有向圖, 確定了本原有向圖的m-competition指數(shù).[關(guān)鍵詞]本原有向圖; m-competition
重慶文理學(xué)院學(xué)報（社會科學(xué)版） 2015年5期2016-01-20
- 一個特殊本原有向圖的廣義competition及scrambling指數(shù)
理論設(shè)D是一個有向圖(允許有環(huán)但不能有重復(fù)弧),D的一條長為l的途徑是指連續(xù)的頂點序列 v1,v2,…,vl+1,對所有的 i=1,2,…,l,D中都有從 vi到 vi+1的弧。用記號表示從vi到vj的l長途徑。另外,Dl是一個有向圖,其中當(dāng)且僅當(dāng)在有向圖D中定義1[1]設(shè)有向圖D,若存在1個正整數(shù)l,使得D中的任意2個頂點 x,y(可以相同),在D中都存在從x到y(tǒng)的l長途徑,則稱D是本原有向圖,其中最小的正整數(shù)l稱為本原指數(shù),記為exp(D)。引理1[1
湖南文理學(xué)院學(xué)報(自然科學(xué)版) 2015年1期2015-12-05
- 一類本原有向圖的m-competition指數(shù)及廣義scrambling指數(shù)
幾年來,對本原有向圖本原指數(shù)的研究已擴(kuò)展到對本原有向圖scramling指數(shù)和m-competition指數(shù)的研究,并取得了許多成果。2009年,Akelbek和Kirkland[1]首次提出了本原圖的scrambling指數(shù)的概念,2010年,黃宇飛等[2]以非記憶通訊系統(tǒng)為背景,對 scrambling指數(shù)進(jìn)行了推廣,引入了廣義scrambling指數(shù)的概念。2010年,Hwa Kyung Kim[3]提出了本原圖的m-competition指數(shù)這一概
湖南文理學(xué)院學(xué)報(自然科學(xué)版) 2015年3期2015-12-05
- 本原有向圖的scrambling指數(shù)和m-competition指數(shù)
V，E）是一個有向圖，其點集V=V（D），邊集E=E（D）.可以有環(huán)但是不能有重弧.用Cp來表示一個長度為p的圈.一個有向圖D是本原的，當(dāng)且僅當(dāng)存在正整數(shù)k，使得D中的任意一點x到另外一點y（y可能等于x）都存在k長途徑.這樣的最小的正整數(shù)k就是有向圖D的本原指數(shù)，用exp（D）表示.在2009年，Akelbek和Kirkland［1］共同提出了本原有向圖scrambling的指數(shù)這一概念.在本原有向圖D中，如果對于任意一對頂點u，v，都能在D中找到一個頂
中北大學(xué)學(xué)報(自然科學(xué)版) 2015年6期2015-12-02
- 一類含三個圈的本原有向圖的m-competition指數(shù)
預(yù)備知識本原有向圖本原指數(shù)［1］的研究已經(jīng)逐步擴(kuò)展到了對本原有向圖的scrambling指數(shù)［2-3］的研究.本原有向圖的scrambling指數(shù)是一個新興研究分支，也是近兩年來在組合數(shù)學(xué)中較為活躍的一個研究方向，在計算機(jī)科學(xué)中具有廣泛的實際應(yīng)用背景.近年，許多學(xué)者又將scrambling指數(shù)推廣到m-competition指數(shù)［4-8］，進(jìn)行了廣泛的研究.設(shè)D=（V，E）是一個n階有向圖，其中頂點集V=V（D），弧集E=E（D）（允許有環(huán)但無重弧）.一
中北大學(xué)學(xué)報(自然科學(xué)版) 2015年5期2015-12-02
- 兩類本原有向圖的廣義scrambling指數(shù)
玉斌?兩類本原有向圖的廣義scrambling指數(shù)張潔敏，*高玉斌（中北大學(xué)理學(xué)院，山西，太原 030051）對兩類本原有向圖進(jìn)行研究。結(jié)合本原有向圖的特點，對圖中的每一點經(jīng)過長途徑所到達(dá)的點集合進(jìn)行分析，根據(jù)廣義scrambling指數(shù)定義，得到了這兩類本原有向圖的廣義scrambling指數(shù)。本原有向圖；點；途徑；廣義scrambling指數(shù)2009年，Akelbek M 和Kirkland S根據(jù)隨機(jī)矩陣的第二大特征值，在文獻(xiàn)[1]中提出了本原有向圖
井岡山大學(xué)學(xué)報(自然科學(xué)版) 2015年1期2015-10-13
- 有向圖出控制數(shù)與入控制數(shù)的和
361005)有向圖出控制數(shù)與入控制數(shù)的和郝國亮*,錢建國(廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005)設(shè)S是有向圖D的一個頂點子集,若D的每個不在S中的頂點都鄰接自(到)S的某個(些)頂點,則稱S是D的出(入)控制集.D的出(入)控制數(shù)是D的出(入)控制集的最小基數(shù).給出了有向圖關(guān)于出控制數(shù)與入控制數(shù)之和的上界,部分改進(jìn)了Chartrand等給出的相應(yīng)結(jié)果.出控制數(shù);入控制數(shù);有向圖1 預(yù)備知識隨著計算機(jī)科學(xué)和網(wǎng)絡(luò)通信技術(shù)的發(fā)展,圖的控制集(domina
廈門大學(xué)學(xué)報（自然科學(xué)版） 2015年3期2015-06-23
- 一類雙色有向圖的本原指數(shù)的上界
00）一類雙色有向圖的本原指數(shù)的上界李 茜1，羅美金2*（1.山西運城農(nóng)業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)部，山西 運城 044000；2.河池學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 宜州 546300）研究一類雙色有向圖，其基礎(chǔ)有向圖僅包含兩個圈，分別是n-圈與（3n-1）-圈，并給出了這個雙色有向圖的本原條件、本原指數(shù)上界，以及對達(dá)到上界的極圖進(jìn)行了刻畫.雙色有向圖；本原指數(shù)；極圖一個雙色有向圖是指其弧被著色為紅色、藍(lán)色的有向圖.若對D的任一對頂點（i，j），都有從i到j(luò)的途徑
海南師范大學(xué)學(xué)報（自然科學(xué)版） 2015年1期2015-04-18
- 一個特殊本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)
)一個特殊本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)張佩1, 王卓宇2, 高玉斌1(1.中北大學(xué) 數(shù)學(xué)系, 山西 太原 030051;2.東華大學(xué) 理學(xué)院, 上海 201620)主要研究一個含有6個圈的n階本原有向圖,其中包含1個n-1圈,3個n-2圈和2個n-3圈.結(jié)合圖論與組合論的相關(guān)知識,得出該圖的scrambling指數(shù)和廣義scrambling指數(shù).本原有向圖; scrambling指數(shù); 廣義scrambling指數(shù);途
商丘師范學(xué)院學(xué)報 2015年3期2015-03-03
- 一個含4個圈的本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)
含4個圈的本原有向圖的scrambling指數(shù)及廣義scrambling指數(shù)申佳，高玉斌(中北大學(xué) 數(shù)學(xué)系，山西 太原 030051)通過分析圖中每一點通過t長途徑所到達(dá)頂點的集合及頂點的個數(shù),并且結(jié)合圖論及組合數(shù)學(xué)的知識,得到一個含有兩個s圈和兩個s-1圈的本原有向圖的scrambling指數(shù)以及廣義scrambling指數(shù).本原有向圖;途徑；scrambling指數(shù);廣義scrambling指數(shù)0 引 言目前, 對本原有向圖的本原指數(shù)的研究已擴(kuò)展到對本
商丘師范學(xué)院學(xué)報 2015年6期2015-03-03
- 一類本原有向圖D的scrambling指數(shù)及廣義scrambling指數(shù)
51)一類本原有向圖D的scrambling指數(shù)及廣義scrambling指數(shù)甄琳，雷英杰(中北大學(xué)數(shù)學(xué)系，山西太原030051)對含有3個圈的n階本原有向圖D的scrambling指數(shù)進(jìn)行研究，通過分析每一點經(jīng)過t長途徑可到達(dá)的點的集合，并根據(jù)本原有向圖的scrambling指數(shù)和廣義scrambling指數(shù)的定義，分別得出該圖的scrambling指數(shù)和λ重下μ-scrambling指數(shù)的精確值，也得到了λ重上μ-scrambling指數(shù)的上界.本原有
重慶文理學(xué)院學(xué)報（社會科學(xué)版） 2014年5期2014-09-19
- 一類非負(fù)本原矩陣對
它所對應(yīng)的伴隨有向圖中含有兩個圈γ1,γ2，公共弧γ1-1→γ1，證明了這類雙色有向圖本原的充分必要條件，并給出了γ2的頂點數(shù)為最小值2時的本原指數(shù)上界。非負(fù)；本原；矩陣對；上界0 引言n階非負(fù)矩陣對(A,B)與其具有n個頂點的伴隨有向圖D(A,B)存在一一對應(yīng)關(guān)系。D(A,B)中弧存在與否可由非負(fù)矩陣對(A,B)中元素的數(shù)值來判斷。如：D(A,B)中是否存在紅弧(藍(lán)弧)可由矩陣A=(aij)(B=(bij))中元素的數(shù)值可判斷，若aij>0(bij>0)
荊楚理工學(xué)院學(xué)報 2014年4期2014-09-04
- 非極大弧連通有向圖弧連通度的下界
）非極大弧連通有向圖弧連通度的下界王曉麗1，王世英2（1．晉中學(xué)院數(shù)學(xué)學(xué)院，山西 榆次 030600；2．山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）設(shè)D是一個有向圖，δ（D）是最小度，弧連通度為λ（D），則λ（D）≤δ（D）。當(dāng)λ（D）＜δ（D）時，稱有向圖D是非極大弧連通的。本文給出了非極大弧連通圖的弧連通度的下界。有向圖；弧連通度；度序列；團(tuán)數(shù)1 引言如果D的任意兩個不同的頂點u，v，在D中都存在（u，v）－路，則稱D為強(qiáng)連通的。對于強(qiáng)連通有向圖
山東科學(xué) 2014年1期2014-06-05
- 基于邊收縮的最優(yōu)裝配序列求解方法
首先擴(kuò)展裝配有向圖結(jié)點的信息為一個邊被收縮圖，在此基礎(chǔ)上給出擴(kuò)展的裝配有向圖的概念，接著通過連續(xù)的邊收縮生成擴(kuò)展的裝配有向圖. 為了便于裝配序列評價，又給出了裝配任務(wù)有向圖的概念，并將擴(kuò)展的裝配有向圖轉(zhuǎn)換成裝配任務(wù)有向圖，最后采用動態(tài)規(guī)劃算法在裝配任務(wù)有向圖中搜索從初始任務(wù)到終止任務(wù)的最短路徑以求解最優(yōu)裝配序列.裝配有向圖；邊被收縮圖；裝配過程；動態(tài)規(guī)劃1 引言產(chǎn)品裝配成本約占產(chǎn)品制造成本的一半，為了降低產(chǎn)品的制造成本，需要獲取產(chǎn)品的最優(yōu)裝配序列.裝配序
玉林師范學(xué)院學(xué)報 2014年5期2014-03-02
- 一個本原有向圖的scrambling指數(shù)和廣義scrambling指數(shù)
ng指數(shù)是本原有向圖的一個新興研究分支.scrambling指數(shù)的研究是基于矩陣(或有向圖)的本原性特征，它在經(jīng)濟(jì)學(xué)、生物學(xué)、化學(xué)、計算機(jī)科學(xué)等眾多學(xué)科中都具有廣泛的應(yīng)用和重要的研究意義.2009年，Mahmud Akelbek和Steve Kirkland在文獻(xiàn)[1]中給出了有關(guān)本原有向圖scrambling指數(shù)的定義，并且討論了一類最小圈長為s的n階本原有向圖的指數(shù)的上界.同年，兩位作者又在文獻(xiàn)[2]中對達(dá)到scrambling指數(shù)的上界K(n，s)的
長春師范大學(xué)學(xué)報 2014年8期2014-01-02
- 兩類n階本原有向圖的廣義competition指數(shù)
ng指數(shù)的本原有向圖，文獻(xiàn)［4］中，Hwa Kyung K im和Sung Gi P ark引入本原有向圖的廣義competition指數(shù)的定義，文獻(xiàn)［4－8］得到了一些本原有向圖的廣義competition指數(shù)，并進(jìn)行了極圖刻畫．本文將研究兩類n階本原有向圖的廣義competition指數(shù)．文章中所涉及到的符號表示的含義詳見文獻(xiàn)［4］［7］［8］．定義1 設(shè)D是n階本原有向圖．如果存在正整數(shù)k，對D中任意頂點vi和vj，總存在w∈V(D)，這里w可能與v
商丘師范學(xué)院學(xué)報 2013年6期2013-11-06
- 一類特殊雙色有向圖的指數(shù)界
引言設(shè)D是一個有向圖，D的一條長為l的途徑是指連續(xù)的頂點序列v1，v2，…，vl+1，其中對所有的i=1，2，…，l，D 中有從 vi到 vi+1的?。绻?v1，v2，…，vl+1互不相同，則稱該途徑是一條長為 l的路．如果 v1=vl+1，則稱為一條閉路或圈．如果D是包含紅弧和藍(lán)弧的有向圖，則稱D是一個雙色有向圖．雙色有向圖D是強(qiáng)連通的，如果D中每一對頂點(i，j)都存在從i到j(luò)的途徑．給定D中的一條途徑ω，用r(ω)和b(ω)－分別表示ω中紅弧和藍(lán)弧
商丘師范學(xué)院學(xué)報 2013年3期2013-07-12
- 一類雙色有向圖的極圖刻畫
00）一類雙色有向圖的極圖刻畫羅美金，侯宗毅，喬友付（河池學(xué)院 數(shù)學(xué)系，廣西 宜州 546300）考慮一類雙色有向圖，它的未著色圖中含一個m-圈和一個n-圈，且兩圈有兩條公共弧，給出了本原條件和并對達(dá)到指數(shù)上界的極圖進(jìn)行了刻畫.雙色；有向圖；指數(shù)；上界；極圖1 引言設(shè)D是一個有向圖，如果D是包含紅弧和藍(lán)弧的有向圖，則稱D是一個雙色有向圖.雙色有向圖D是強(qiáng)連通的，如果D中每一對頂點(i,j)都存在從i到j(luò)的途徑.給定D中的一條途徑ω，用r(ω)和b(ω)分別
赤峰學(xué)院學(xué)報·自然科學(xué)版 2012年11期2012-10-16
- 一類特殊本原有向圖的廣義的scrambling指數(shù)
n圈的n階本原有向圖，D中最小圈長為s，且1≤s≤n-1 ，如果 gcd(n，s)=1 ，則有：k(D) ≤ K(n，s)=n-s+k(n，s) ．其中定理 3［2］設(shè) D=Ds，n，gcd(n，s)=1 ，2≤ s≤ n-1，則有k(D)=K(n，s)．1 主要結(jié)論引理4 已知D是如圖1所示的本原有向圖，則有圖1 本原有向圖D［1］Huang Yufei，Liu Bolian．Generalized scrambling indices of a pri
重慶高教研究 2012年4期2012-10-08
- 2個特殊本原有向圖的Scrambling指數(shù)與廣義Scrambling指數(shù)
）2個特殊本原有向圖的Scrambling指數(shù)與廣義Scrambling指數(shù)代愛鳳，邵燕靈（中北大學(xué) 數(shù)學(xué)系，太原 030051）考慮2個含有3個圈（其中2個圈的長度相等但不相交）的特殊本原有向圖.通過分析圖中每一點經(jīng)過t長途徑所到達(dá)的點的集合及點的個數(shù)，給出了此類圖的Scrambling指數(shù)和廣義Scrambling指數(shù).本原有向圖；Scrambling指數(shù)；廣義Scrambling指數(shù)1 基本概念設(shè)D為有向圖，如果存在正整數(shù)l，使得對于D的任意頂點x、
天津師范大學(xué)學(xué)報（自然科學(xué)版） 2012年3期2012-01-04
- 無環(huán)的本原反對稱帶號有向圖的局部基與基指數(shù)
10631)稱有向圖D是本原的,如果存在正整數(shù)k使得對于D中任意2點vi和vj(允許i=j),在D中都有從點vi到點vj的長為k的有向途徑.這樣的最小正整數(shù)k稱為D的本原指數(shù),記為exp(D).有向圖D是本原的,當(dāng)且僅當(dāng)D是強(qiáng)連通的,且其所有有向圈長的最大公約數(shù)為1.設(shè)W1與W2是帶號有向圖S中的2條有向途徑，如果W1與W2有相同的起點、相同的終點、相同的長度,并且有不同的符號,則稱W1與W2是一個SSSD途徑對.如果S中不包含SSSD途徑對,則稱帶號有向
華南師范大學(xué)學(xué)報（自然科學(xué)版） 2011年1期2011-11-27
- 兩類本原不可冪定號有向圖基的界?
aij≠0}的有向圖稱為 A的伴隨有向圖(可能有環(huán)),記為 D(A).將 D(A)中每條弧(i,j)賦予 aij得到的圖稱為 A的伴隨定號有向圖,記為 S(A).反過來,給出一個 n階定號有向圖 S,一定存在 n階符號模式矩陣 A,使得 A的伴隨定號有向圖是 S.因此符號模式矩陣和定號有向圖之間存在一一對應(yīng)的關(guān)系.設(shè) D是有向圖,若(i0,i1),(i1,i2),… ,(ik-1,ik)是 D的弧,則弧的序列(i0,i1),(i1,i2),… ,(ik-1
中北大學(xué)學(xué)報(自然科學(xué)版) 2011年5期2011-09-11
- 某類本原不可冪定號有向圖的基指數(shù)
1或0.將一個有向圖D(允許含有環(huán)但不能有重弧)中的每一條弧賦予符號1或-1所得的圖稱為D的定號有向圖.定號有向圖中的一條途徑W是由一系列的弧e1,e2,…,ek組成的,并且ei的終點與ei+1的起點相同 (i=1,Λ,κ-1).途徑W中所含弧的條數(shù)稱為途徑W的長度,記為l(W)[1].途徑W的符號定義為W中所有弧的符號的乘積(重復(fù)出現(xiàn)的弧的符號重復(fù)計),即設(shè) D為有向圖,如果存在正整數(shù) k,使得對于 D中的任意頂點νi和νj(可以相同)都有從νi到νj的
河北北方學(xué)院學(xué)報（自然科學(xué)版） 2011年4期2011-02-28
- 含三個圈的本原不可冪定號有向圖的基
原矩陣 (本原有向圖)的本原指數(shù)的研究進(jìn)展非常迅速,許多問題已經(jīng)圓滿解決.定義1[1]如果 n階有向圖D是某個n階本原矩陣的伴隨有向圖,則稱D為n階本原有向圖,簡稱n階本原圖.稱A的本原指數(shù)ν(A)為本原有向圖D的本原指數(shù),記為ν(D).本原指數(shù)的研究最早開始于1950年Wielandt的工作,給出了n階本原指數(shù)的一般性上界1964年,Dulmage和M endelsohn創(chuàng)造性的運用有向圖理論,得出了 n階本原指數(shù)的一般性上界的另一種形式其中s是A的伴隨
河北北方學(xué)院學(xué)報（自然科學(xué)版） 2011年4期2011-02-28
- 一個恰含三個圈的本原不可冪定號有向圖的基
本原不可冪定號有向圖的基趙 晶，高玉斌（中北大學(xué) 理學(xué)院，山西 太原 030051）為了進(jìn)一步了解本原不可冪定號有向圖的基的特點及有關(guān)性質(zhì)，對一個特殊的本原不可冪定號有向圖的基進(jìn)行了研究．通過分析這個圖的特點，運用反證法并結(jié)合圖中的本原指數(shù)、點指數(shù)、基指數(shù)、Frobenius集、可冪與不可冪及“異圈對”等定義和性質(zhì)得出基的具體值．本原；定號有向圖；不可冪；基0 引言一個實數(shù)a的符號sgna，根據(jù)a＞ 0，a＜ 0或a= 0，被定義為1，?1或0．將一個有向
天中學(xué)刊 2011年5期2011-01-12
- ＊ 蘊含強(qiáng)(p,q)哈密爾頓性的幾個條件
,證明了,如果有向圖D滿足下列條件中的任何一個,(1)最小半度δ0(D)≥(n+p+q)/2;(2)D是(p+q+1)強(qiáng)連通有向圖,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,這里,x,y是任意控制頂點對,u,v是任意被控制頂點對;(3)D的弧數(shù)超過(n-1)2+q2+p;那么D是強(qiáng)(p,q)哈密爾頓的.路收縮;最小半度;度和;最少弧數(shù);強(qiáng)(p,q)哈密爾頓O157.5A本文僅考慮無環(huán)、無重邊的有向圖.設(shè)D是一個有向圖,我們用n
山西大學(xué)學(xué)報（自然科學(xué)版） 2011年1期2011-01-11
- 限制弧連通有向圖的充分條件
6）限制弧連通有向圖的充分條件伊 輝 王世英（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）強(qiáng)連通；圍長；強(qiáng)分支；限制弧連通度0 引言設(shè)D＝（V（D），A（D））是沒有環(huán)和重弧的有限有向圖，其中V（D）和A（D）分別是D的頂點集和弧集.D的頂點數(shù)n＝|V（D）|稱為D的階.若弧uv∈A（D），則稱u控制v，記為u→v，稱u和v分別為弧uv的尾和頭.頂點v∈V（D）的出度d＋（v）＝（v）是D中v抽控制的頂點數(shù)，入度d－（v）＝（v）是D中控制v的頂點數(shù)
太原師范學(xué)院學(xué)報(自然科學(xué)版) 2011年3期2011-01-09
- 一類特殊本原不可冪定號有向圖的local基
本原不可冪定號有向圖的local基張 波，栗 慧，邵燕靈（中北大學(xué) 數(shù)學(xué)系，太原 030051）對一類特殊的含有3個圈的本原不可冪定號有向圖的local基進(jìn)行了研究.運用“異圈對”、Frobenius集及本原指數(shù)等討論圖中是否有相應(yīng)的SSSD途徑對，得到了這類圖的local基與基.local基；定號有向圖；本原將有向圖D（可能含有環(huán)）中的每一條弧定義一個符號1或－1所得的圖稱為D的定號有向圖，記為S，D稱為S的基礎(chǔ)有向圖.定義1［1］如果定號有向圖S中不含
天津師范大學(xué)學(xué)報（自然科學(xué)版） 2011年2期2011-01-04
- 一類非負(fù)矩陣對的本原指數(shù)
一類特殊的雙色有向圖,它的未著色圖中含有 3n-2個頂點,包含一個(2n+1)-圈和一個n-圈的圖,給出了本原條件和指數(shù)的上、下界,并對極圖進(jìn)行了刻劃.本原指數(shù);本原圖;雙色圖;指數(shù)界;極圖0 引言設(shè)D是一個有向圖,D的一條長為l的途徑是指連續(xù)的頂點序列v1,v2,……,vl+1,其中對所有的i=1,2,……,l,D中都有從vi到vi+1的弧.如果v1,v2,……,vl+1,互不相同,則稱該途徑是一條長為l的路.如果vi=vi+1,則稱為一條閉路或圈.如果
河池學(xué)院學(xué)報 2010年2期2010-12-22
- 一類含有兩個m-圈的三色有向圖的本原指數(shù)
個m-圈的三色有向圖的本原指數(shù)劉海琴(山西農(nóng)業(yè)大學(xué)文理學(xué)院,山西太谷 030801)對于一個三色有向圖D,其本原的定義是指當(dāng)且僅當(dāng)存在非負(fù)整數(shù)h,k,l,并且有h+k+l＞0,使得對于D中的每一對頂點(i,j)都存在從i到j(luò)的(h,k,l)-途徑,定義h+k+l的最小值為D的本原指數(shù)。研究了一類特殊的三色有向圖,其未著色圖恰含一個bm-1-圈、二個m-圈,并且研究了該圖在一種本原條件下的三色有向圖的本原指數(shù)。三色有向圖;本原條件;本原指數(shù)非負(fù)矩陣組合理論是
- 一類恰含兩個圈的本原不可冪定號有向圖的廣義基
本原不可冪定號有向圖的廣義基霍麗芳1,2,高玉斌1(1.中北大學(xué)理學(xué)院,山西太原030051;2.河北建筑工程學(xué)院數(shù)理系,河北張家口075024)研究了一類恰含兩個圈的本原不可冪定號有向圖,通過分析圖形特點,綜合利用 SSSD途徑對和Frobenius指數(shù)的特性推導(dǎo)出這類圖的廣義基.本原圖;定號有向圖;SSSD途徑對;廣義本原指數(shù);廣義基1 基本概念定義1.1 設(shè)D是一個有向圖 (允許有環(huán)但不能有重弧),如果存在一個正整數(shù) k,使得 D中任意兩個頂點vi和
河北北方學(xué)院學(xué)報（自然科學(xué)版） 2010年1期2010-01-17
- 有向圖是極大弧連通的充分條件
自環(huán)和平行弧的有向圖.設(shè)點 v∈V,分別用 d-D(v)、d+D(v)(簡寫為,d-(v)、d+(v)),記為 v的出度、入度,δ-(D)、δ+(D)為 D的最小入度、最小出度,且D的最小度記為,δ(D)=min{δ-(D),δ+(D)}.強(qiáng)連通有向圖D的弧割,是指去掉這個弧割后D不再強(qiáng)連通.弧連通度λ(D)是一個最小弧割的基數(shù).D是極大弧連通的,如果λ=δ.設(shè)X,Y?V,且(X,Y)表示尾巴在X中,頭在 Y中的弧集.和 K→n,m分別是完全有向圖與完全二
成都大學(xué)學(xué)報（自然科學(xué)版） 2010年4期2010-01-10