QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 6437|回复: 1
打印 上一主题 下一主题

[问题求助] 求助关于求图割点的代码,哪里错了?怎么改正啊?

[复制链接]
字体大小: 正常 放大

9

主题

7

听众

188

积分

升级  44%

  • TA的每日心情
    慵懒
    2013-8-23 15:15
  • 签到天数: 84 天

    [LV.6]常住居民II

    自我介绍
    我想参加明年的数模竞赛

    群组西安交大数学建模

    群组数学建摸协会

    群组英语科技论文写作实训

    跳转到指定楼层
    #
    发表于 2013-3-3 14:54 |只看该作者 |正序浏览
    |招呼Ta 关注Ta
    2体力
    function [nc] = ncutf(g)
    6 w; H* J" f5 F  j%求割点的算法 g为邻接矩阵 nc为割点的集合
    ) R4 _" c# |2 j* x* w7 qn=size(g,1);
    % [: i( N% h: ?, M7 J) k* N4 Sif n>=3
    ; O( z' f2 D0 i4 i) {% e# N) J& Y    a=sum(g);1 F* m5 |& f6 b0 e; I
        b=sum(a==2);4 g# p; d1 C2 \! B
        if b==n
    0 q# a1 z& P5 X        fprintf('本图为圈,无割点。n')
    5 Q9 R1 ~; }) I8 F: i8 h: u        nc=0;
    ' Z6 `: ~5 b, A! y    end- f! `$ G+ x* ~2 j0 i1 ~1 q
    else
    0 Z' [/ W+ c" `- d! }    [w,k]=dfs3(g);
    ' c& [* R) F2 `    %nc=[];% y; S# j* N4 V+ Q3 E0 Y' @
        nc=isncf(w,k);
    ! Y  c8 C& X9 f0 [9 X* y* W5 }) |) I    n=size(g,1);
    + M/ Z/ G/ L# g    for i=1:n
    ' b; U: \& T; a6 K        for j=1:n
    6 T- f; i* {# ~            if w(i,j)>19 d/ W4 z1 X. P
                    if k(i)>k(j)
    . k/ q1 g9 E, ^" E                    g(i,j)=2;' T& [  n. a$ f; E9 }' L4 m! T7 f
                    else; S8 ~, V$ e  f! |* N9 r
                        g(i,j)=3;. [& ]& x: ~6 |9 c( q! P
                    end& v0 J& H8 @. T! T! d6 x
                end
    ( z! D' `  i, T2 a        end6 _' k; `( V( u- R
        end8 o9 z& T$ D8 V) C
        & _+ O& S0 M# y3 _
        for i=1:n8 C* U! T4 C1 ]
            f1=find(g(i,==2);
    8 M# A1 j$ B$ m+ l* C        f2=find(g(i,==3);
    . ~: Y& c$ S+ M$ ~0 B3 _; i        f=union(f1,f2);
    ! r( d$ N/ }, n" O. q6 n+ [7 z; t        l(i)=min([k(f) k(i)]);. H* ?1 }4 m% |; s# k: h. Y9 i
        end% r/ P7 B* a% A6 `  R1 L
        ) w$ c0 q2 S3 R( I; F0 D0 p! ^9 v) p
        for i=1:n3 r( v: Y% W2 i: Q$ a2 J" f9 u
            for j=1:n6 @' x( R+ j9 D9 |9 S& _* o$ U8 Z
                if g(i,j)==3 & k(i)>1&l(j)>=k(i): g" W& o5 T8 f, d
                    nc=union(i,nc);
    5 @! N( u- `& g' x            end
    7 }( z8 \' A$ i. w( c        end
    # _! h& n0 Y  y3 ]% K    end, n  |, ?# c: y' R2 P
    end
    * W8 P  u$ l0 N5 }8 Bend! L* h! B1 J" C3 `( h

    3 ~* P' Z8 W$ x. V0 i+ b: f
    % k/ t8 B) h8 R0 x# t! [function nc=isncf(w,k)
      i7 l0 B, C+ |: a  T0 `    nc=[];
    8 \2 o7 L' w7 N    t=zeros(size(w));
    + ?4 N/ K0 O. m4 N    n=size(w,1);
    1 q& e5 e6 x7 {/ M    a=find(w~=0);  C: e. R1 [: T& r* s0 e: k
        for i=1:length(a)! S3 M% x; W* T" _8 L2 o' }
            d(i)=w(a(i));; |& P7 _+ m& A: t) w* O8 x) j( T
            if a(i)/n>floor(a(i)/n)" w/ z6 T) b9 H; a6 ~; h9 ^/ C
              t(i)=floor(a(i)/n)+1;9 z6 l- E1 Y, d) Y
            else( N: C+ }6 V& j0 w
                t(i)=floor(a(i)/n);7 t2 t5 k! P4 i# J$ M' d
            end
    ) i4 k2 j: R9 f( e- _( }6 d        t1(i)=mod(a(i),n);
    % _3 d$ p5 d$ n        if t1(i)==0, S3 B0 Y5 S+ i+ @
                t1(i)=n;
    ; z9 F* `# w: t0 T& z        end
    7 k( U4 s, r4 x# y  o0 k: k  m/ h    end
    4 E0 y& t7 W- _  ]4 L  q    [b,c]=sort(d);9 K8 ]; U2 V% E2 ]" j
        p=[1];pc=0;
    - Y/ e' {( \& C6 O    for i=1:length(a)
    ; E1 \& \- V- J- v* h) B        if k(t1(c(i)))<k(t(c(i))): a4 Z% D1 p# t) {' M) z
                p=union(p,t(c(i)));
    ( `; `2 ~: L5 S! l            t(t1(c(i)),t(c(i)))=3;
      v0 G* T+ M6 z+ M8 a6 r! X2 w        end
    4 ^& a& @* i2 k+ v; j% s        if pc==0# N: r" ]  u# N, I- j4 X
                tc=isempty(setdiff([1:n],p));
    9 F8 ~* D* }. H: ?! n            if tc
      n' E7 q! [8 U0 a' V2 A. @                t0=sum(t(1,==3);. k- m( G4 J; K4 R3 O" A+ |' c
                    if  t0>=2' A) J5 Z) ]8 z0 m. g
                        nc=union(nc,1);: C  F( X. C% M4 o' Q4 M
                    end% U0 n' U* A2 M8 K0 V- i2 N: |
                    break;8 O$ i4 a7 Q# ~1 }
                end
    . H5 `& B9 ~- V        end
    + q/ N, z) _0 Z- _2 i6 c2 O) Z    end
    4 q6 @; ~. p, D8 M    6 I& i! k9 U* L
            ( z$ U( L, T& i9 {( w; P2 Q# q" Y% H
    end

    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    9

    主题

    7

    听众

    188

    积分

    升级  44%

  • TA的每日心情
    慵懒
    2013-8-23 15:15
  • 签到天数: 84 天

    [LV.6]常住居民II

    自我介绍
    我想参加明年的数模竞赛

    群组西安交大数学建模

    群组数学建摸协会

    群组英语科技论文写作实训

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-13 16:03 , Processed in 0.442195 second(s), 60 queries .

    回顶部